Submission #1500586

---

Source Code Expand

from collections import defaultdict

def hamiltonish_path():
	n, m = map(int, raw_input().split(" "))
	edges = defaultdict(list)
	for i in range(m):
		a = map(str, raw_input().split(" "))
		edges[a[0]].append(a[1])
		edges[a[1]].append(a[0])
	from collections import deque
	# print edges
	ans = deque(['1'])
	satisfy = False
	while not satisfy:
		left_head = ans[0]
		right_head = ans[-1]
		x = len(ans)
		for n in edges[left_head]:
			if n not in ans:
				ans.appendleft(n)
				break
		for n in edges[right_head]:
			if n not in ans:
				ans.append(n)
				break

		if x==len(ans):
			satisfy=True
	print len(ans)
	print " ".join(ans)

if __name__ == "__main__":
	hamiltonish_path()

Submission Info

Judge Result