AtCoder Grand Contest 013 - Hamiltonish Path

You are given a connected undirected simple graph, which has N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertices A_i and B_i. Your task is to find a path that satisfies the following conditions:

* The path traverses two or more vertices.
* The path does not traverse the same vertex more than once.
* A vertex directly connected to at least one of the endpoints of the path, is always contained in the path.



It can be proved that such a path always exists. Also, if there are more than one solution, any of them will be accepted.

Constraints

* 2 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq A_i < B_i \leq N
* The given graph is connected and simple (that is, for every pair of vertices, there is at most one edge that directly connects them).

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
A_2 B_2
:
A_M B_M


Output

Find one path that satisfies the conditions, and print it in the following format. In the first line, print the count of the vertices contained in the path. In the second line, print a space-separated list of the indices of the vertices, in order of appearance in the path.

Examples

Input

5 6
1 3
1 4
2 3
1 5
3 5
2 4


Output

4
2 3 1 4


Input

7 8
1 2
2 3
3 4
4 5
5 6
6 7
3 5
2 6


Output

7
1 2 3 4 5 6 7

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(N, M) = map(int, input().split())
edge = [set([]) for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	edge[a - 1].add(b - 1)
	edge[b - 1].add(a - 1)
visit = set([0])
ans = [0]
pos = 0
while True:
	for i in edge[pos]:
		if i not in visit:
			ans.append(i)
			visit.add(i)
			pos = i
			break
	else:
		break
ans = ans[::-1]
pos = ans[-1]
while True:
	for i in edge[pos]:
		if i not in visit:
			ans.append(i)
			visit.add(i)
			pos = i
			break
	else:
		break
for i in range(len(ans)):
	ans[i] += 1
print(len(ans))
print(*ans)


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
G = [[] for i in range(N + 5)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
ans = []
used = [False] * (N + 5)

def dfs(u):
	global ans
	used[u] = True
	ans.append(u)
	for w in G[u]:
		if not used[w]:
			dfs(w)
			return
	return
dfs(1)
ans = ans[::-1]
ans = ans[:-1]
dfs(1)
print(len(ans))
print(*ans)


import sys
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
seen = [False] * n

def dfs(v, rep):
	seen[v] = True
	for nv in G[v]:
		if seen[nv]:
			continue
		rep.append(nv + 1)
		dfs(nv, rep)
		break
	else:
		return rep
(L1, L2) = ([], [])
dfs(0, L1)
dfs(0, L2)
ANS = L2[::-1] + [1] + L1
print(len(ANS))
print(*ANS)


from collections import deque

def remove(adj, a):
	for nxt in adj[a]:
		adj[nxt].remove(a)

def main():
	(N, M) = map(int, input().split())
	adj = [set() for _ in range(N + 1)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		adj[a].add(b)
		adj[b].add(a)
	ans = deque([a, b])
	remove(adj, b)
	remove(adj, a)
	first = a
	last = b
	while len(adj[first]):
		nxt = list(adj[first])[0]
		ans.appendleft(nxt)
		remove(adj, nxt)
		first = nxt
	remove(adj, first)
	for a in ans:
		if a in adj[last]:
			adj[last].remove(a)
	while len(adj[last]):
		nxt = list(adj[last])[0]
		ans.append(nxt)
		remove(adj, nxt)
		last = nxt
	print(len(ans))
	print(*ans)
main()


(N, M, *AB) = map(int, open(0).read().split())
E = [[] for _ in range(N + 1)]
for (a, b) in zip(*[iter(AB)] * 2):
	E[a].append(b)
	E[b].append(a)
visited = [False] * (N + 1)
visited[a] = True
visited[b] = True
A = [a]
while True:
	for v in E[a]:
		if not visited[v]:
			A.append(v)
			visited[v] = True
			a = v
			break
	else:
		break
B = [b]
while True:
	for v in E[b]:
		if not visited[v]:
			B.append(v)
			visited[v] = True
			b = v
			break
	else:
		break
ans = A[::-1] + B
print(len(ans))
print(*ans)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def graph_input(N, M):
	G = [[] for _ in range(N + 1)]
	for _ in range(M):
		(a, b) = map(int, readline().split())
		G[a].append(b)
		G[b].append(a)
	return G
(N, M) = map(int, readline().split())
G = graph_input(N, M)
visited = [0] * (N + 1)
a = 1
b = G[a][0]
Pa = [a]
Pb = [b]
visited[a] = 1
visited[b] = 1
while True:
	v = Pa[-1]
	for w in G[v]:
		if visited[w]:
			continue
		visited[w] = 1
		Pa.append(w)
		break
	if v == Pa[-1]:
		break
while True:
	v = Pb[-1]
	for w in G[v]:
		if visited[w]:
			continue
		visited[w] = 1
		Pb.append(w)
		break
	if v == Pb[-1]:
		break
P = Pa[::-1] + Pb
print(len(P))
print(*P)


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	(n, m) = map(int, input().split())
	E = [[] for _ in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		E[a].append(b)
		E[b].append(a)
	used = [0] * n
	used[0] = 1
	Q = [0]
	front = [0]
	while Q:
		v = Q.pop()
		for nv in E[v]:
			if used[nv]:
				continue
			used[nv] = 1
			front.append(nv)
			Q.append(nv)
			break
	back = []
	Q = [0]
	while Q:
		v = Q.pop()
		for nv in E[v]:
			if used[nv]:
				continue
			used[nv] = 1
			back.append(nv)
			Q.append(nv)
			break
	ans = back[::-1] + front
	print(len(ans))
	print(*map(lambda x: x + 1, ans))
resolve()


import sys
from collections import deque, defaultdict
INF = float('inf')
MOD = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def II():
	return int(sys.stdin.readline())

def SI():
	return input()

def main():
	(n, m) = LI()
	G = defaultdict(list)
	S = defaultdict(set)
	for _ in range(m):
		(a, b) = LI_()
		G[a].append(b)
		G[b].append(a)
		S[a].add(b)
		S[b].add(a)
	res = deque([0, G[0][0]])
	visited = set(res)
	needs = S[res[0]] | S[res[-1]] - visited
	while needs:
		v = needs.pop()
		if v in visited:
			continue
		visited.add(v)
		if v in S[res[0]]:
			res.appendleft(v)
		else:
			res.append(v)
		needs = (S[res[0]] | S[res[-1]]) - visited
	print(len(res))
	print(*[v + 1 for v in res])
main()


(N, M) = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
seen = [0] * (N + 1)

def move(start):
	ret = []
	v = start
	seen[v] = 1
	while True:
		finish = 1
		for u in adj[v]:
			if seen[u] == 0:
				ret.append(u)
				seen[u] = 1
				v = u
				finish = 0
				break
		if finish:
			break
	return ret
fwd = move(1)
bwd = move(1)
bwd.reverse()
ans = bwd
ans.append(1)
ans.extend(fwd)
print(len(ans))
print(*ans)


(n, m) = map(int, input().split())
edges = {}
for _ in range(m):
	(a, b) = map(int, input().split())
	if a - 1 in edges:
		edges[a - 1].append(b - 1)
	else:
		edges[a - 1] = [b - 1]
	if b - 1 in edges:
		edges[b - 1].append(a - 1)
	else:
		edges[b - 1] = [a - 1]
(end1, end2) = (a - 1, b - 1)
visited = [False for _ in range(n)]
visited[end1] = True
visited[end2] = True
seti = set([end1, end2])
path = [end1, end2]
while True:
	reme = None
	for _a in edges[end1]:
		if _a not in seti:
			reme = _a
			break
	if reme is not None:
		end1 = _a
		seti.add(_a)
		path = [_a] + path
	else:
		for _a in edges[end2]:
			if _a not in seti:
				reme = _a
				break
		if reme is not None:
			end2 = _a
			seti.add(_a)
			path += [_a]
	if reme is None:
		break
print(len(path))
print(*map(lambda x: x + 1, path))


max2 = lambda x, y: x if x > y else y
min2 = lambda x, y: x if x < y else y
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(N, edges):
	adj = [[] for _ in range(N)]
	for (a, b) in edges:
		adj[a].append(b)
		adj[b].append(a)
	visited = [False] * N
	right = []
	v = 0
	visited[v] = True
	while True:
		for u in adj[v]:
			if not visited[u]:
				right.append(u)
				v = u
				visited[v] = True
				break
		else:
			break
	left = []
	v = 0
	while True:
		for u in adj[v]:
			if not visited[u]:
				left.append(u)
				v = u
				visited[v] = True
				break
		else:
			break
	left.reverse()
	return left + [0] + right
(N, M) = map(int, readline().split())
m = map(lambda x: int(x) - 1, read().split())
path = solve(N, zip(m, m))
print(len(path))
print(*(v + 1 for v in path))


(n, m) = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = [int(i) - 1 for i in input().split()]
	e[a].append(b)
	e[b].append(a)
used = [False] * n
used[0] = True
ans1 = [1]
ans2 = []
i = 0
while True:
	for j in e[i]:
		if not used[j]:
			i = j
			ans1.append(j + 1)
			used[j] = True
			break
	else:
		break
i = 0
while True:
	for j in e[i]:
		if not used[j]:
			i = j
			ans2.append(j + 1)
			used[j] = True
			break
	else:
		break
ans = list(reversed(ans2)) + ans1
print(len(ans))
print(' '.join(map(str, ans)))


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
e = dd(list)
inc = [0] * (N + 1)
for _ in range(M):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
	inc[u] += 1
	inc[v] += 1
s = 0
inc[0] = float('inf')
for i in range(N):
	if inc[i] < inc[s]:
		s = i
vis = set()
vis.add(s)
res = []

def dfs(x):
	global vis
	global res
	vis.add(x)
	res.append(x)
	c = 0
	for y in e[x]:
		if y in vis:
			continue
		c += 1
		dfs(y)
	if c == 0:
		for y in e[s]:
			if not y in vis:
				c += 1
		if c == 0:
			print(len(res))
			print(*res)
			exit(0)
	res.pop()
	vis.discard(x)
dfs(s)


import sys, math, copy
from collections import deque
HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = 'abcdefghijklmnopqrstuvwxyz'

def adj_node(path, paths, neighbor):
	for end in [path[0], path[-1]]:
		for node in neighbor[end - 1]:
			if node not in paths:
				is_begin = end == path[0]
				return (node, is_begin)
	return (None, True)

def get_path():
	(n, m) = map(int, input().split())
	am = []
	bm = []
	for i in range(m):
		(a, b) = map(int, input().split())
		am.append(a)
		bm.append(b)
	assert len(am) == len(bm) == m
	neighbor = [[] for j in range(n)]
	for i in range(m):
		(a, b) = (am[i], bm[i])
		neighbor[a - 1].append(b)
		neighbor[b - 1].append(a)
	path = deque([am[0], bm[0]])
	paths = set(path)
	for j in range(10 ** 6):
		(node, is_begin) = adj_node(path, paths, neighbor)
		if node is None:
			return path
		paths.add(node)
		if is_begin:
			path.appendleft(node)
		else:
			path.append(node)

def main():
	path = get_path()
	print(len(path))
	print(' '.join(map(str, path)))
main()


(N, M) = list(map(int, input().split()))
e_list = [[] for i in range(N)]
for i in range(M):
	(a, b) = list(map(int, input().split()))
	(a, b) = (a - 1, b - 1)
	e_list[a].append(b)
	e_list[b].append(a)
vi = 0
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi] = True
chain = []
while len(Q) > 0:
	v = Q.pop()
	chain.append(v + 1)
	checked_list[v] = True
	flag = True
	for v1 in e_list[v]:
		if not checked_list[v1]:
			flag = False
			Q.append(v1)
	if flag:
		break
Q = deque([vi])
chain1 = []
while len(Q) > 0:
	v = Q.pop()
	chain1.append(v + 1)
	checked_list[v] = True
	flag = True
	for v1 in e_list[v]:
		if not checked_list[v1]:
			flag = False
			Q.append(v1)
	if flag:
		break
chain1 = chain1[::-1]
ans = chain1[:-1] + chain
print(len(ans))
print(*ans)


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 5)

def li():
	return map(int, stdin.readline().split())

def li_():
	return map(lambda x: int(x) - 1, stdin.readline().split())

def lf():
	return map(float, stdin.readline().split())

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(stdin.readline())

def nf():
	return float(stdin.readline())
from collections import deque
(n, m) = li()
graph = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = li_()
	graph[a].append(b)
	graph[b].append(a)
	path = deque([a, b])
path_set = set(path)
ed = b
satisfied = False
while not satisfied:
	satisfied = True
	for nex in graph[ed]:
		if nex in path_set:
			continue
		else:
			path_set.add(nex)
			path.append(nex)
			ed = nex
			satisfied = False
			break
ed = a
satisfied = False
while not satisfied:
	satisfied = True
	for nex in graph[ed]:
		if nex in path_set:
			continue
		else:
			path_set.add(nex)
			path.appendleft(nex)
			ed = nex
			satisfied = False
			break
path = [pi + 1 for pi in path]
print(len(path))
print(*path)


from collections import deque
(n, m) = map(int, input().split())
edges = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	edges[a].append(b)
	edges[b].append(a)
ans = deque([1, edges[1][0]])
used = [False] * (n + 1)
(used[1], used[edges[1][0]]) = (True, True)
while True:
	ok = True
	for e in edges[ans[0]]:
		if used[e] == False:
			ans.appendleft(e)
			used[e] = True
			ok = False
			break
	for e in edges[ans[-1]]:
		if used[e] == False:
			ans.append(e)
			used[e] = True
			ok = False
			break
	if ok:
		break
print(len(ans))
print(*ans)


import sys
import os

def print_matrix(M):
	print('matrix')
	for (i, row) in enumerate(M):
		print(i, end=': ')
		print(row)
(N, E) = list(map(int, input().split()))
M = [[] for j in range(N)]
for _ in range(E):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	M[a].append(b)
	M[b].append(a)
visited = [False] * N

def get_path(start_index):
	answer = []
	answer.append(start_index)
	visited[start_index] = True
	current_index = start_index
	while True:
		candidates = M[current_index]
		next_index = None
		for candidate_i in candidates:
			if not visited[candidate_i]:
				next_index = candidate_i
				visited[candidate_i] = True
				break
		if next_index is not None:
			answer.append(next_index)
			visited[next_index] = True
			current_index = next_index
		else:
			break
	return answer

def check_condition(path):
	left_index = path[0]
	destinations = M[left_index]
	for dest in destinations:
		if not visited[dest]:
			return (False, dest)
	right_index = path[-1]
	destinations = M[right_index]
	for dest in destinations:
		if not visited[dest]:
			return (False, dest)
	return (True, None)
full_path = []
next_index = 0
while True:
	path = get_path(next_index)
	if full_path:
		path.reverse()
		full_path = path + full_path
	else:
		full_path = path
	check_result = check_condition(full_path)
	if check_result[0]:
		break
	else:
		next_index = check_result[1]
print(len(full_path))
answer2 = []
for v in full_path:
	answer2.append(str(v + 1))
print(' '.join(answer2))


from collections import defaultdict, deque

def main():
	(N, M) = list(map(int, input().split()))
	adj = defaultdict(list)
	(A, B) = (-1, -1)
	for _ in range(M):
		(A, B) = list(map(lambda x: int(x) - 1, input().split()))
		adj[A].append(B)
		adj[B].append(A)
	visited = [0] * N
	visited[A] = 1
	visited[B] = 1
	from_a = list()
	que = deque([A])
	while len(que) > 0:
		n = que.pop()
		from_a.append(n)
		visited[n] = 1
		all_visited = True
		for next_n in adj[n]:
			if visited[next_n] == 1:
				continue
			que.append(next_n)
			all_visited = False
		if all_visited:
			break
	from_b = list()
	que = deque([B])
	while len(que) > 0:
		n = que.pop()
		from_b.append(n)
		visited[n] = 1
		all_visited = True
		for next_n in adj[n]:
			if visited[next_n] == 1:
				continue
			que.append(next_n)
			all_visited = False
		if all_visited:
			break
	ans = from_a[::-1] + from_b
	ans = [x + 1 for x in ans]
	print(len(ans))
	print(' '.join(map(str, ans)))
main()


from collections import deque
(n, m) = map(int, input().split())
e = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	e[a].append(b)
	e[b].append(a)
l = deque([1])
s = set([1])
while True:
	check = True
	for nex in e[l[-1]]:
		if nex in s:
			continue
		l.append(nex)
		s.add(nex)
		check = False
		break
	if check:
		break
while True:
	check = True
	for nex in e[l[0]]:
		if nex in s:
			continue
		l.appendleft(nex)
		s.add(nex)
		check = False
		break
	if check:
		print(len(l))
		print(*l)
		exit()


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	n = I()
	a = LI()
	u = [0] * n
	r = 1
	for l in range(n):
		if l == r:
			r += 1
		while r < n and a[r - 1] <= a[r]:
			r += 1
		u[l] = r
	d = [0] * n
	r = 1
	for l in range(n):
		if l == r:
			r += 1
		while r < n and a[r - 1] >= a[r]:
			r += 1
		d[l] = r
	i = 0
	for t in range(n):
		i = max(u[i], d[i])
		if i == n:
			print(t + 1)
			return
	return

def B():
	(n, m) = LI()
	v = [[] for i in range(n)]
	for i in range(m):
		(a, b) = LI()
		a -= 1
		b -= 1
		v[a].append(b)
		v[b].append(a)
	f = [1] * n
	p = deque([0])
	f[0] = 0
	update = 1
	while update:
		update = 0
		x = p[0]
		for y in v[x]:
			if f[y]:
				update = 1
				f[y] = 0
				p.appendleft(y)
				break
		x = p[-1]
		for y in v[x]:
			if f[y]:
				update = 1
				f[y] = 0
				p.append(y)
				break
	p = list(p)
	for i in range(len(p)):
		p[i] += 1
	print(len(p))
	print(*p)
	return

def C():
	return

def D():
	return

def E():
	return

def F():
	return
B()


(N, M, *L) = map(int, open(0).read().split())
dic = [[] for i in range(N + 1)]
for (a, b) in zip(*[iter(L)] * 2):
	dic[a].append(b)
	dic[b].append(a)
log = set([1])
pre = [1]
p = 1
while True:
	for v in dic[p]:
		if v not in log:
			break
	else:
		break
	p = v
	pre.append(v)
	log.add(v)
ans = pre[::-1]
p = 1
while True:
	for v in dic[p]:
		if v not in log:
			break
	else:
		break
	p = v
	ans.append(v)
	log.add(v)
print(len(ans))
print(' '.join(map(str, ans)))


from collections import deque
(N, M) = map(int, input().split())
e = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	e[a].append(b)
	e[b].append(a)
ans = [0]
ans = deque(ans)
in_path = [False] * N
in_path[0] = True
while True:
	f = ans[0]
	for v in e[f]:
		if not in_path[v]:
			ans.appendleft(v)
			in_path[v] = True
			break
	else:
		break
while True:
	b = ans[-1]
	for v in e[b]:
		if not in_path[v]:
			ans.append(v)
			in_path[v] = True
			break
	else:
		break
print(len(ans))
print(*list(map(lambda x: x + 1, ans)))


(n, m) = map(int, input().split())
edge = [set() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	edge[a].add(b)
	edge[b].add(a)
closed_path = set()
n = 1
answer = []
while True:
	answer.append(n)
	closed_path.add(n)
	for i in edge[n]:
		if i not in closed_path:
			n = i
			break
	else:
		break
n = 1
answer.reverse()
del answer[-1]
while True:
	answer.append(n)
	closed_path.add(n)
	for i in edge[n]:
		if i not in closed_path:
			n = i
			break
	else:
		break
print(len(answer))
print(*answer)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(n, m) = map(int, readline().split())
data = list(map(int, read().split()))
links = [set() for _ in range(n + 1)]
it = iter(data)
for (a, b) in zip(it, it):
	links[a].add(b)
	links[b].add(a)
ans = [1]
done = [0] * (n + 1)
done[1] = 1
now = 1
while links[now]:
	i = links[now].pop()
	if done[i] == 1:
		continue
	done[i] = 1
	ans.append(i)
	now = i
ans = ans[::-1]
now = 1
while links[now]:
	i = links[now].pop()
	if done[i] == 1:
		continue
	done[i] = 1
	ans.append(i)
	now = i
print(len(ans))
print(' '.join(map(str, ans)))


from collections import *
import sys
S = sys.stdin.readlines()
(N, M) = map(int, S[0].split())
G = [[] for i in range(N)]
(a, b) = (0, 0)
for i in range(M):
	(a, b) = map(int, S[i + 1].split())
	(a, b) = (a - 1, b - 1)
	G[a].append(b)
	G[b].append(a)
P = deque([0, G[0][0]])
U = [1] * N
U[0] = 0
U[G[0][0]] = 0
F = 0
while True:
	for i in range(len(G[P[0]])):
		if U[G[P[0]][i]]:
			U[G[P[0]][i]] = 0
			P.appendleft(G[P[0]][i])
			break
	else:
		break
while True:
	for i in range(len(G[P[-1]])):
		if U[G[P[-1]][i]]:
			U[G[P[-1]][i]] = 0
			P.append(G[P[-1]][i])
			break
	else:
		break
print(len(P))
Q = []
for i in range(len(P)):
	Q.append(P.popleft() + 1)
print(*Q)


import sys
input = sys.stdin.readline
from collections import deque
(N, M) = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)
path = deque(AB[0])
visited = set(AB[0])
while True:
	x = path[0]
	update = False
	for y in graph[x]:
		if y not in visited:
			path.appendleft(y)
			visited.add(y)
			update = True
			break
	if not update:
		break
while True:
	x = path[-1]
	update = False
	for y in graph[x]:
		if y not in visited:
			path.append(y)
			visited.add(y)
			update = True
			break
	if not update:
		break
print(len(path))
print(*path)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	es[a].append(b)
	es[b].append(a)
from collections import deque
q = deque([0, es[0][0]])
st = set([0, es[0][0]])
while 1:
	(a, b) = (q[0], q[-1])
	for to in es[a]:
		if to in st:
			continue
		st.add(to)
		q.appendleft(to)
		break
	else:
		for to in es[b]:
			if to in st:
				continue
			st.add(to)
			q.append(to)
			break
		else:
			print(len(q))
			print(*[a + 1 for a in q])
			exit()


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for m in range(M):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	G[a].append(b)
	G[b].append(a)
visited = set()
(ans1, ans2) = ([], [])
ans1.append(str(1))
visited.add(0)

def dfs(n, ans):
	for ni in G[n]:
		if ni not in visited:
			ans.append(str(ni + 1))
			visited.add(ni)
			dfs(ni, ans)
			break
dfs(0, ans1)
dfs(0, ans2)
print(len(ans1) + len(ans2))
print(' '.join(ans2[::-1] + ans1))


(n, m) = map(int, input().split())
g = [set() for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].add(b)
	g[b].add(a)
start = 0
spath = {0}
path = [0]
todo = [0]
next = g[0].pop()
spath.add(next)
path.append(next)
while g[path[-1]]:
	next = g[path[-1]].pop()
	if next not in spath:
		spath.add(next)
		path.append(next)
rpath = [0]
while g[rpath[-1]]:
	next = g[rpath[-1]].pop()
	if next not in spath:
		spath.add(next)
		rpath.append(next)
rpath.reverse()
rpath.pop()
rpath += path
rpath = [i + 1 for i in rpath]
print(len(rpath))
print(*rpath, sep=' ')


(N, M) = map(int, input().split())
E = [set() for i in range(N + 1)]
for i in range(M):
	(A, B) = map(int, input().split())
	E[A].add(B)
	E[B].add(A)
Closed = set()
n = 1
Ans = []
while True:
	Ans.append(n)
	Closed.add(n)
	for e in E[n]:
		if e not in Closed:
			n = e
			break
	else:
		break
n = 1
Ans.reverse()
del Ans[-1]
while True:
	Ans.append(n)
	Closed.add(n)
	for e in E[n]:
		if e not in Closed:
			n = e
			break
	else:
		break
print(len(Ans))
print(*Ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
edge = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	edge[a].append(b)
	edge[b].append(a)
s = set()
left = right = 0
s.add(0)
from collections import deque
q = deque()
q.append(0)
f_left = True
f_right = True
while f_left or f_right:
	if f_left:
		m = -1
		for to in edge[left]:
			if to not in s:
				m = to
		if m >= 0:
			left = m
			s.add(m)
			q.appendleft(m)
		else:
			f_left = False
	if f_right:
		m = -1
		for to in edge[right]:
			if to not in s:
				m = to
		if m >= 0:
			right = m
			s.add(m)
			q.append(m)
		else:
			f_right = False
print(len(q))
print(*[i + 1 for i in list(q)])


(N, M) = map(int, input().split())
graph = [[] for i in range(N + 1)]
for i in range(M):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
is_visited = [False] * (N + 1)
is_visited[1] = True
ans = [1]

def add_node(start):
	global is_visited
	global ans
	now = start
	go_next = True
	while go_next:
		go_next = False
		nodes = graph[now]
		for node in nodes:
			if not is_visited[node]:
				ans.append(node)
				is_visited[node] = True
				now = node
				go_next = True
				break
add_node(1)
ans = ans[::-1]
add_node(1)
print(len(ans))
print(*ans)


from collections import deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
e = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	e[a].append(b)
	e[b].append(a)
l = deque([1])
visit = [0] * (n + 1)
visit[1] = 1
while True:
	check = True
	for nex in e[l[-1]]:
		if visit[nex]:
			continue
		l.append(nex)
		visit[nex] = 1
		check = False
		break
	if check:
		break
while True:
	check = True
	for nex in e[l[0]]:
		if visit[nex]:
			continue
		l.appendleft(nex)
		visit[nex] = 1
		check = False
		break
	if check:
		print(len(l))
		print(*l)
		exit()


import sys
from heapq import heappop, heappush
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))

def dijkstra(start):
	INF = 10 ** 7
	dist = [INF] * (N + 1)
	dist[start] = 0
	que = [(0, start)]
	while que:
		(d, prev) = heappop(que)
		if dist[prev] < d:
			continue
		for next in graph[prev]:
			d1 = d + 1
			if dist[next] > d1:
				dist[next] = d1
				heappush(que, (d1, next))
	return dist
(N, M) = lr()
graph = [[] for _ in range(N + 1)]
for _ in range(M):
	(a, b) = lr()
	graph[a].append(b)
	graph[b].append(a)
dig_1 = [i for i in range(1, N + 1) if len(graph[i]) == 1]
if len(dig_1) >= 2:
	start = dig_1[0]
	goal = dig_1[1]
	dist_from_start = dijkstra(start)
	dist_from_goal = dijkstra(goal)
	d = dist_from_start[goal]
	answer = [None] * (d + 1)
	answer[0] = start
	cur = start
	for i in range(1, d + 1):
		for next in graph[cur]:
			if dist_from_goal[next] == d - i:
				answer[i] = next
				cur = next
				break
	print(d + 1)
	print(*answer)
elif len(dig_1) == 1:
	start = dig_1[0]
	answer = [start]
	visited = set()
	cur = start
	while True:
		flag = True
		for next in graph[cur]:
			if next not in visited:
				flag = False
				visited.add(next)
				answer.append(next)
				cur = next
				break
		if flag:
			break
	print(len(answer))
	print(*answer)
else:
	start = 1
	answer = [start]
	visited = set([1])
	cur = start
	while True:
		flag = True
		for next in graph[cur]:
			if next not in visited:
				flag = False
				visited.add(next)
				answer.append(next)
				cur = next
				break
		if flag:
			break
	answer = answer[::-1]
	cur = start
	while True:
		flag = True
		for next in graph[cur]:
			if next not in visited:
				flag = False
				visited.add(next)
				answer.append(next)
				cur = next
				break
		if flag:
			break
	print(len(answer))
	print(*answer)


(N, M) = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
L = [[] for _ in range(N)]
for (a, b) in AB:
	a -= 1
	b -= 1
	L[a].append(b)
	L[b].append(a)
D = [False] * N
D[0] = True
t = 0
Ans = [1]
while True:
	for x in L[t]:
		if not D[x]:
			t = x
			D[x] = True
			Ans.append(x + 1)
			break
	else:
		break
t = 0
Ans = Ans[::-1]
while True:
	for x in L[t]:
		if not D[x]:
			t = x
			D[x] = True
			Ans.append(x + 1)
			break
	else:
		break
print(len(Ans))
print(' '.join(list(map(str, Ans))))


(N, M) = map(int, input().split())
from collections import deque, defaultdict
branch = defaultdict(set)
for i in range(M):
	(a, b) = map(int, input().split())
	branch[a - 1] |= {b - 1}
	branch[b - 1] |= {a - 1}
path = deque([0])
for x in branch[0]:
	path.append(x)
	break
used = set(path)
while True:
	(A, B) = (False, False)
	if len(branch[path[0]] - used) == 0:
		A = True
	else:
		for x in branch[path[0]]:
			if x in used:
				continue
			path.appendleft(x)
			used |= {x}
			break
	if len(branch[path[-1]] - used) == 0:
		B = True
	else:
		for x in branch[path[-1]]:
			if x in used:
				continue
			path.append(x)
			used |= {x}
			break
	if A and B:
		break
path = [p + 1 for p in path]
print(len(path))
print(' '.join(map(str, path)))


import sys
sys.setrecursionlimit(2 * 10 ** 5)
(N, M) = map(int, input().split())
(A, B) = zip(*(map(int, input().split()) for _ in range(M)))
E = [[] for _ in range(N + 1)]
for (a, b) in zip(A, B):
	E[a].append(b)
	E[b].append(a)
v = [i == 1 for i in range(N + 1)]

def dfs(i, p):
	for j in E[i]:
		if not v[j]:
			v[j] = True
			p.append(j)
			return dfs(j, p)
	else:
		return p
p = list(reversed(dfs(1, []))) + [1] + dfs(1, [])
ans = '{}\n{}'.format(len(p), ' '.join(map(str, p)))
print(ans)


(N, M) = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	es[a].append(b)
	es[b].append(a)
start = 0
visited = [0] * N
ans = [[], []]
for i in range(2):
	stack = [start]
	visited[start] = 0
	while stack:
		v = stack.pop()
		visited[v] = 1
		ans[i].append(v)
		finish = 1
		for to in es[v]:
			if visited[to]:
				continue
			stack.append(to)
			finish = 0
		if finish:
			break
ans = ans[0][::-1] + ans[1][1:]
print(len(ans))
print(' '.join(list(map(lambda x: str(x + 1), ans))))


(n, m) = map(int, input().split())
c = []
for i in range(m):
	c.append([int(m) for m in input().split()])
graph = {}
for i in range(n):
	graph[i + 1] = []
for i in range(m):
	graph[c[i][0]] = graph[c[i][0]] + [c[i][1]]
	graph[c[i][1]] = graph[c[i][1]] + [c[i][0]]
stack = []
start = 1
i = start
visited = set()
visited.add(i)
root = [i]
while True:
	for j in graph[i]:
		if j not in visited:
			i = j
			root += [i]
			visited.add(i)
			break
	else:
		break
i = 1
root2 = []
while True:
	for j in graph[i]:
		if j not in visited:
			i = j
			root2 += [i]
			visited.add(i)
			break
	else:
		break
ver = len(root2) + len(root)
print(ver)
root = root2[::-1] + root
for i in root:
	print(i, '', end='')


from collections import deque as dq
(N, M) = map(int, input().split())
Graph = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	Graph[a - 1].append(b - 1)
	Graph[b - 1].append(a - 1)
path = dq(['1', str(Graph[0][0] + 1)])
p = [False] * N
ep1 = 0
ep2 = Graph[0][0]
(p[ep1], p[ep2]) = (True, True)
flag = 0
while len(path) <= N:
	for a in Graph[ep1]:
		if not p[a]:
			path.appendleft(str(a + 1))
			p[a] = True
			ep1 = a
			flag = 1
			break
	for b in Graph[ep2]:
		if not p[b]:
			path.append(str(b + 1))
			p[b] = True
			ep2 = b
			flag = 1
			break
	if flag == 0:
		print(len(path))
		print(' '.join(path))
		exit()
	flag = 0


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
[n, m] = i2()
e = [[] for i in range(n + 100)]
for i in range(m):
	[a, b] = i2()
	e[a].append(b)
	e[b].append(a)
import sys
sys.setrecursionlimit(10 ** 6)
d = [0 for i in range(n + 100)]
dd = []

def dfs1(v):
	d[v] = 1
	for i in e[v]:
		if d[i] == 0:
			dd.append(i)
			dfs1(i)
			break
ddd = []

def dfs2(v):
	d[v] = 1
	for i in e[v]:
		if d[i] == 0:
			ddd.append(i)
			dfs2(i)
			break
dfs1(1)
dfs2(1)
l = ddd[::-1] + [1] + dd
print(len(l))
print(*l)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
start = -1
for v in range(n):
	if len(g[v]) == 0:
		continue
	start = v
	break
memo = [0] * n
memo[start] = 1
count = 0
q1 = deque([])
q2 = deque([])
for v in g[start]:
	if memo[v] == 1:
		continue
	count += 1
	if count > 2:
		break
	memo[v] = 1
	if count == 1:
		q1.append(v)
	elif count == 2:
		q2.append(v)
ans1 = [start]
while q1:
	node = q1.popleft()
	ans1.append(node)
	flag = 0
	for nv in g[node]:
		if memo[nv] == 1:
			continue
		memo[nv] = 1
		q1.append(nv)
		flag = 1
		break
	if flag == 0:
		break
ans2 = []
while q2:
	node = q2.popleft()
	ans2.append(node)
	flag = 0
	for nv in g[node]:
		if memo[nv] == 1:
			continue
		memo[nv] = 1
		q2.append(nv)
		flag = 1
		break
	if flag == 0:
		break
ans1 = ans1[::-1]
ans = []
for i in ans1:
	ans.append(i + 1)
for i in ans2:
	ans.append(i + 1)
print(len(ans))
print(*ans)


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

def solve():

	def dfs1(u, path, visited):
		for w in Adj[u]:
			if not visited[w]:
				path.append(w)
				visited[w] = True
				dfs1(w, path, visited)
				return

	def dfs2(u, path, visited):
		for w in Adj[u]:
			if not visited[w]:
				path.appendleft(w)
				visited[w] = True
				dfs2(w, path, visited)
				return
	(N, M) = map(int, sys.stdin.readline().split())
	Adj = [[] for i in range(N)]
	for i in range(M):
		(a, b) = map(int, sys.stdin.readline().split())
		(a, b) = (a - 1, b - 1)
		Adj[a].append(b)
		Adj[b].append(a)
	if any((len(v) == 1 for v in Adj)):
		for (i, v) in enumerate(Adj):
			if len(v) == 1:
				s = i
				break
		path = [s]
		visited = [False] * N
		visited[s] = True
		dfs1(s, path, visited)
		path = [i + 1 for i in path]
		print(len(path))
		print(*path)
	else:
		s = 0
		path = deque([0])
		visited = [False] * N
		visited[s] = True
		dfs1(s, path, visited)
		dfs2(s, path, visited)
		path = [i + 1 for i in path]
		print(len(path))
		print(*path)

def debug(x, table):
	for (name, val) in table.items():
		if x is val:
			print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
			return None
solve()


import collections
I = [int(_) for _ in open(0).read().split()]
(N, M) = I[:2]
(A, B) = (I[2::2], I[3::2])
G = collections.defaultdict(set)
for (a, b) in zip(A, B):
	G[a].add(b)
	G[b].add(a)
ans = []
seen = set()
x = 1
while True:
	ans += [x]
	seen.add(x)
	allseen = True
	for y in G[x]:
		if y not in seen:
			allseen = False
			x = y
			break
	if allseen:
		break
ans = ans[:0:-1]
x = 1
while True:
	ans += [x]
	seen.add(x)
	allseen = True
	for y in G[x]:
		if y not in seen:
			allseen = False
			x = y
			break
	if allseen:
		break
print(len(ans))
print(*ans)


(N, M) = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
used = [False] * N
used[0] = used[edge[0][0]] = True
path = [0, edge[0][0]]

def not_use(v):
	for e in edge[v]:
		if used[e]:
			continue
		else:
			return e
	return -1

def append():
	while True:
		v = not_use(path[-1])
		if v < 0:
			break
		else:
			path.append(v)
			used[v] = True

def main():
	append()
	path.reverse()
	append()
	ans = [v + 1 for v in path]
	print(len(ans))
	print(*ans, sep=' ')
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def rec(u, prev, li):
	li.append(u + 1)
	visited[u] = 1
	for v in nodes[u]:
		if v != prev and visited[v] == -1:
			if rec(v, u, li):
				return True
	return True
(N, M) = MAP()
nodes = [[] for i in range(N)]
visited = [-1] * N
for i in range(M):
	(a, b) = MAP()
	a -= 1
	b -= 1
	nodes[a].append(b)
	nodes[b].append(a)
ans = []
rec(0, -1, ans)
ans = ans[1:][::-1]
rec(0, -1, ans)
print(len(ans))
print(*ans)


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
sys.setrecursionlimit(10000)

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv(N, M, AB):
	g = defaultdict(set)
	for (a, b) in AB:
		g[a].add(b)
		g[b].add(a)
	path = deque([1])
	path.append(list(g[1])[0])
	path_s = set(path)
	while not (g[path[0]] | g[path[-1]]).issubset(path_s):
		l = g[path[0]] - path_s
		if l:
			for v in l:
				path.appendleft(v)
				path_s.add(v)
				break
			continue
		r = g[path[-1]] - path_s
		if r:
			for v in r:
				path.append(v)
				path_s.add(v)
				break
			continue
	print(len(path))
	print(' '.join(map(lambda x: str(x), path)))

def main():
	(N, M) = read_int_n()
	AB = [read_int_n() for _ in range(M)]
	slv(N, M, AB)
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
(N, M) = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(M):
	(A, B) = map(int, input().split())
	v[A - 1].append(B - 1)
	v[B - 1].append(A - 1)
visited = [False] * N
visited[0] = True
path = [[], []]

def dfs(cur, mode):
	flag = True
	for nex in v[cur]:
		if visited[nex]:
			continue
		flag = False
		visited[nex] = True
		f = dfs(nex, mode)
		visited[nex] = False
		if f:
			path[mode].append(cur + 1)
			return True
	if flag:
		if mode == 0:
			dfs(0, 1)
		path[mode].append(cur + 1)
		return True
	return False
dfs(0, 0)
ret = path[0][:-1] + path[1][::-1]
print(len(ret))
print(*ret)


(N, M) = map(int, input().split())
Edge = [[] for i in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	Edge[a - 1].append(b - 1)
	Edge[b - 1].append(a - 1)
Used = [False for i in range(N)]
Path = [1, Edge[0][0] + 1]
(Used[0], Used[Edge[0][0]]) = (True, True)
(AFin, BFin) = (False, False)
(Anext, Bnext) = (0, Edge[0][0])
for node in Edge[0]:
	if not Used[node]:
		Anext = node
		Used[Anext] = True
		break
else:
	AFin = True
for node in Edge[Bnext]:
	if not Used[node]:
		Bnext = node
		Used[Bnext] = True
		break
else:
	BFin = True
while not AFin or not BFin:
	if not AFin:
		Path.insert(0, Anext + 1)
		for node in Edge[Anext]:
			if not Used[node]:
				Anext = node
				Used[Anext] = True
				break
		else:
			AFin = True
	if not BFin:
		Path.append(Bnext + 1)
		for node in Edge[Bnext]:
			if not Used[node]:
				Bnext = node
				Used[Bnext] = True
				break
		else:
			BFin = True
print(len(Path))
print(' '.join(map(str, Path)))


(N, M) = list(map(int, input().split(' ')))
e = [[] for i in range(N)]
for i in range(M):
	(a, b) = list(map(int, input().split(' ')))
	a -= 1
	b -= 1
	e[a].append(b)
	e[b].append(a)
ch = [False for i in range(N)]
right = []
ch[0] = True
now = 0
while 1:
	for i in e[now]:
		if ch[i] == False:
			ch[i] = True
			now = i
			right.append(i)
			break
	else:
		break
left = []
now = 0
while 1:
	for i in e[now]:
		if ch[i] == False:
			ch[i] = True
			now = i
			left.append(i)
			break
	else:
		break
res = left[::-1] + [0] + right
for i in range(len(res)):
	res[i] = str(res[i] + 1)
print(len(res))
print(' '.join(res))


import heapq

def dijkstra_path(V, source, target):
	visited = [False] * V
	prev = [-1 for i in range(V)]
	dist = [float('inf')] * V
	dist[source] = 0
	h = [(0, source)]
	while h:
		(c, v) = heapq.heappop(h)
		if visited[v]:
			continue
		visited[v] = True
		for i in range(len(graph[v])):
			t = graph[v][i]
			nc = c + 1
			if dist[t] > nc:
				dist[t] = nc
				heapq.heappush(h, (nc, t))
				prev[t] = v
	path = [target]
	while path[-1] != source and path[-1] != -1:
		path.append(prev[path[-1]])
	return path[::-1]

def all_contains(s, a):
	return all([x in s for x in a])
(n, m) = map(int, input().split())
graph = [[] for i in range(n)]
cnt = [0 for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
	cnt[a - 1] += 1
	cnt[b - 1] += 1
start = 0
end = 1
for i in range(n):
	if cnt[i] <= cnt[start]:
		end = start
		start = i

def main():
	v = start
	path = [start]
	moved = [0 for i in range(n)]
	pre = [float('inf') for i in range(n)]
	while True:
		if path[-1] != v:
			path.append(v)
		if all_contains(path, graph[v]) and all_contains(path, graph[start]):
			return path
		while moved[v] < len(graph[v]):
			nv = graph[v][moved[v]]
			if nv not in path:
				pre[nv] = v
				moved[v] += 1
				v = nv
				break
			else:
				moved[v] += 1
		else:
			path.pop()
			moved[v] = 0
			v = pre[v]

def allow_path(path):
	for i in range(len(path) - 1):
		if not path[i + 1] in graph[path[i]]:
			print(i + 1, path[i + 1], 'not in ', graph[path[i]])
			return False
	return True
if cnt[end] == 1:
	res = dijkstra_path(n, start, end)
else:
	res = main()
print(len(res))
print(' '.join([str(x + 1) for x in res]))


from collections import deque
(N, M) = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
seen = [0] * (N + 1)
seen[1] = 1
ans = deque([1])
s = 1
while True:
	update = False
	for t in edge[s]:
		if seen[t]:
			continue
		update = True
		seen[t] = 1
		break
	if not update:
		break
	ans.append(t)
	s = t
s = 1
while True:
	update = False
	for t in edge[s]:
		if seen[t]:
			continue
		update = True
		seen[t] = 1
		break
	if not update:
		break
	ans.appendleft(t)
	s = t
print(len(ans))
print(*ans)


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n + 1)]
for (a, b) in ab:
	graph[a].append(b)
	graph[b].append(a)
vis = [0 for i in range(n + 1)]
vis[1] = 1
stack = [1]
ans = deque()
while stack:
	x = stack.pop()
	flg = 0
	ans.append(x)
	for y in graph[x]:
		if vis[y] == 0:
			stack.append(y)
			vis[y] = 1
			flg = 1
			break
	if not flg:
		break
stack = [1]
while stack:
	x = stack.pop()
	flg = 0
	if x != 1:
		ans.appendleft(x)
	for y in graph[x]:
		if vis[y] == 0:
			stack.append(y)
			vis[y] = 1
			flg = 1
			break
	if not flg:
		break
print(len(ans))
print(*ans)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
g = tuple((set() for _ in range(n)))
for _ in range(m):
	(a, b) = (int(x) - 1 for x in input().split())
	g[a].add(b)
	g[b].add(a)

def choose_an_edge():
	for (a, st) in enumerate(g):
		if st:
			for b in st:
				return (a, b)
(a, b) = choose_an_edge()
dq = deque()
dq.append(a)
dq.append(b)
used = [False] * n
used[a] = True
used[b] = True

def dfs(v, add_prev=False) -> None:
	for u in g[v]:
		if used[u]:
			continue
		if add_prev:
			dq.appendleft(u)
		else:
			dq.append(u)
		used[u] = True
		dfs(u, add_prev=add_prev)
		return
dfs(a, add_prev=True)
dfs(b, add_prev=False)
print(len(dq))
print(*map(lambda x: x + 1, dq))


(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
d = {}
for (i, j) in a:
	d[i] = d.get(i, set()) | {j}
	d[j] = d.get(j, set()) | {i}
path = a[0][:]
sp = set(path)
while d[path[-1]] - sp:
	t = d[path[-1]] - sp
	t = t.pop()
	path.append(t)
	sp.add(t)
path = path[::-1]
while d[path[-1]] - sp:
	t = d[path[-1]] - sp
	t = t.pop()
	path.append(t)
	sp.add(t)
print(len(path))
print(*path)


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
node = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	node[a - 1].append(b)
	node[b - 1].append(a)
d = deque()
d.append(1)
d.append(node[0][0])
s = set(d)
f = True
while True:
	f = True
	for i in node[d[0] - 1]:
		if i not in s:
			d.appendleft(i)
			s.add(i)
			f = False
			break
	for i in node[d[-1] - 1]:
		if i not in s:
			d.append(i)
			s.add(i)
			f = False
			break
	if f:
		print(len(d))
		print(*d)
		exit()


(n, m, *t) = map(int, open(0).read().split())
e = [[] for _ in range(n + 1)]
for (a, b) in zip(t[::2], t[1::2]):
	e[a].append(b)
	e[b].append(a)
f = [0] * -~n
f[1] = 1
a = [1]
while 1:
	for v in e[a[-1]]:
		if not f[v]:
			f[v] = 1
			a.append(v)
			break
	else:
		break
b = [1]
while 1:
	for v in e[b[-1]]:
		if not f[v]:
			f[v] = 1
			b.append(v)
			break
	else:
		break
a = a[:0:-1] + b
print(len(a), *a)


import sys
sys.setrecursionlimit(100000)
(N, M) = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
	(A, B) = map(int, input().split())
	edges[A - 1].append(B - 1)
	edges[B - 1].append(A - 1)
visited = [False] * N
path = []

def dfs(curr):
	visited[curr] = True
	path.append(curr)
	for dst in edges[curr]:
		if not visited[dst]:
			dfs(dst)
			return
dfs(0)
path = path[1:][::-1]
dfs(0)
print(len(path))
print(' '.join([str(v + 1) for v in path]))


from collections import deque
(n, m) = map(int, input().split())
g = [list() for _ in range(n + 1)]
(a, b) = map(int, input().split())
(l, r) = (a, b)
s = set([a, b])
q = deque()
q.append(a)
q.append(b)
g[a].append(b)
g[b].append(a)
for _ in range(m - 1):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
f = 1
while f:
	f = 0
	for x in g[l]:
		if x in s:
			continue
		q.appendleft(x)
		l = x
		s.add(x)
		f = 1
		break
f = 1
while f:
	f = 0
	for x in g[r]:
		if x in s:
			continue
		q.append(x)
		r = x
		s.add(x)
		f = 1
		break
print(len(q))
print(' '.join(map(str, q)))


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(v, path):
	for u in g[v]:
		if check[u] == 0:
			check[u] = 1
			path.append(u)
			return dfs(u, path)
	else:
		return path
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
check = [0] * (n + 1)
check[1] = 1
ans = dfs(1, [])[::-1]
ans += [1]
ans += dfs(1, [])
print(len(ans))
print(*ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
R = [1 for i in range(N + 1)]
(A, B) = map(int, input().split())
R[A] = 0
R[B] = 0
L = [[] for i in range(N + 1)]
L[A].append(B)
L[B].append(A)
for i in range(M - 1):
	(a, b) = map(int, input().split())
	L[a].append(b)
	L[b].append(a)
l = [A]
P = A
for i in range(10 ** 6):
	flag = 0
	for j in L[P]:
		if R[j] == 1:
			P = j
			R[j] = 0
			l.append(j)
			flag += 1
			break
	if flag == 0:
		break
r = [B]
P = B
for i in range(10 ** 6):
	flag = 0
	for j in L[P]:
		if R[j] == 1:
			P = j
			R[j] = 0
			r.append(j)
			flag += 1
			break
	if flag == 0:
		break
l = l[::-1]
ans = l + r
print(len(ans))
print(*ans)


from random import *
from functools import reduce, partial

def readln():
	return list(map(int, input().split(' ')))

def identity(x):
	return x

def constant(c):

	def const_function(const, *args):
		return const
	return partial(const_function, c)

def inc(c=1):
	return lambda x: x + c

def add(*args):

	def add2(x, y):
		return x + y
	return reduce(add2, args)

def mapv(f, *lst):
	return list(map(f, *lst))

def vector(*args):
	return args

def sequence(n, f=constant(0)):
	return [f(i) for i in range(0, n)]

def matrix(n, m, f=constant(0)):
	return [[f(i, j) for j in range(0, m)] for i in range(0, n)]

def flat(v):
	if not isinstance(v, list):
		return [v]
	if not v:
		return []
	return reduce(add, mapv(flat, v))

def partition(v, f=identity):
	result = {}
	for item in v:
		key = f(item)
		s = result.get(key)
		if s:
			s.append(item)
		else:
			result.update({key: [item]})
	return result

def getValue(key):
	return lambda x: x[key]

def mapValue(f, m):
	res = {}
	for key in m:
		res.update({key: f(m[key])})
	return res
(n, m) = readln()
e = [set() for i in range(n + 1)]
for i in range(m):
	(s, t) = readln()
	e[s].add(t)
	e[t].add(s)
v = sequence(n + 1, constant(True))
q = sequence(n + 1)
q[0] = 1
p = q[:]
v[1] = False
i = 0
while q[i] > 0:
	s = q[i]
	for t in e[s]:
		if v[t]:
			v[t] = False
			q[i + 1] = t
			break
	i = i + 1
j = 0
while p[j] > 0:
	s = p[j]
	for t in e[s]:
		if v[t]:
			v[t] = False
			p[j + 1] = t
			break
	j = j + 1
print(i + j - 1)
for k in range(1, i):
	print(q[i - k], end=' ')
for k in range(0, j):
	print(p[k], end=' ')


import sys
sys.setrecursionlimit(100005)
(N, M) = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	E[A].append(B)
	E[B].append(A)
visited = [False for _ in range(N)]
ans = []

def dfs(p, one):
	if visited[p]:
		return False
	visited[p] = True
	if not one:
		ans.append(p + 1)
	for i in E[p]:
		if dfs(i, one):
			break
	if one:
		ans.append(p + 1)
	return True
dfs(0, True)
for i in E[0]:
	if dfs(i, False):
		break
print(len(ans))
for i in ans:
	print(i)


from collections import deque
(n, m) = (int(i) for i in input().split())
x = [[] for i in range(n + 1)]
for _ in range(m):
	(a, b) = (int(i) for i in input().split())
	x[a].append(b)
	x[b].append(a)
(s, g, v) = (1, x[1][0], [True] * (n + 1))
ans = deque([s, g])
while True:
	(v[s], v[g], c) = (False, False, 1)
	for i in x[s]:
		if v[i]:
			(s, c) = (i, 0)
			ans.appendleft(i)
			break
	if c:
		for i in x[g]:
			if v[i]:
				(g, c) = (i, 0)
				ans.append(i)
				break
	if c:
		break
print(len(ans))
for i in ans:
	print(i, end=' ')


(N, M) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in [0] * M]
E = [[] for _ in [0] * N]
for (a, b) in AB:
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
done = [False] * N
ans = [[], []]
for k in range(2):
	done[0] = False
	q = [0]
	while q:
		i = q.pop()
		if done[i]:
			continue
		done[i] = True
		for j in E[i]:
			if done[j]:
				continue
			q.append(j)
			ans[k].append(j + 1)
			break
		else:
			break
ans = ans[0][::-1] + [1] + ans[1]
print(len(ans))
print(*ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def main():
	(n, m) = LI()
	d = collections.defaultdict(set)
	for _ in range(m):
		(a, b) = LI()
		d[a].add(b)
		d[b].add(a)
	r = [1, list(d[1])[0]]
	v = collections.defaultdict(bool)
	for c in r:
		v[c] = True
	while True:
		t = r[-1]
		f = True
		for c in d[t]:
			if v[c]:
				continue
			r.append(c)
			v[c] = True
			f = False
			break
		if f:
			break
	r = r[::-1]
	while True:
		t = r[-1]
		f = True
		for c in d[t]:
			if v[c]:
				continue
			r.append(c)
			v[c] = True
			f = False
			break
		if f:
			break
	return '{}\n{}'.format(len(r), ' '.join(map(str, r)))
print(main())


from collections import deque

class Graph:

	def __init__(self, n, edge, indexed=1):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.deg = [0 for _ in range(n)]
		for e in edge:
			self.graph[e[0] - indexed].append(e[1] - indexed)
			self.graph[e[1] - indexed].append(e[0] - indexed)
			self.deg[e[0] - indexed] += 1
			self.deg[e[1] - indexed] += 1
(N, M) = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]
g = Graph(N, E)
used = [0 for _ in range(N)]
res = deque([E[0][0], E[0][1]])
used[res[0] - 1] = 1
used[res[-1] - 1] = 1
flag_lt = True
flag_rt = True
while flag_lt or flag_rt:
	lt = res[0] - 1
	rt = res[-1] - 1
	if flag_lt:
		for adj in g.graph[lt]:
			if not used[adj]:
				used[adj] = 1
				res.appendleft(adj + 1)
				break
		else:
			flag_lt = False
	if flag_rt:
		for adj in g.graph[rt]:
			if not used[adj]:
				used[adj] = 1
				res.append(adj + 1)
				break
		else:
			flag_rt = False
print(len(res))
print(*res)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
edge = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)
c = [1 for i in range(n + 1)]
ans = []

def f(s):
	c[s] = 0
	ans.append(s)
	for i in edge[s]:
		if c[i]:
			return f(i)
f(1)
ans.reverse()
del ans[-1]
f(1)
print(len(ans))
print(' '.join(map(str, ans)))


(n, m) = map(int, input().split())
edges = [set() for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	edges[a - 1].add(b - 1)
	edges[b - 1].add(a - 1)
hei = set()
cur = 0
paths = []
f = False
while True:
	hei.add(cur + 1)
	paths.append(cur + 1)
	for i in edges[cur]:
		if not i + 1 in hei:
			cur = i
			break
	else:
		break
cur = 0
paths = list(reversed(paths[1:]))
f = False
while True:
	hei.add(cur + 1)
	paths.append(cur + 1)
	for i in edges[cur]:
		if not i + 1 in hei:
			cur = i
			break
	else:
		break
print(len(paths))
print(*paths)


import sys
sys.setrecursionlimit(1000000000)
from collections import defaultdict
(N, M) = [int(_) for _ in input().split()]
V = defaultdict(list)
for i in range(M):
	(A, B) = [int(_) for _ in input().split()]
	V[A].append(B)
	V[B].append(A)

def solve(N, M, V):
	result = [1, V[1][0]]
	used = [False] * (N + 1)
	for x in result:
		used[x] = True

	def check_edge(i):
		for e in V[result[i]]:
			if not used[e]:
				if i == -1:
					result.append(e)
				else:
					result.insert(i, e)
				used[e] = True
				return True
		return False
	while True:
		if check_edge(0):
			continue
		if check_edge(-1):
			continue
		return result
result = solve(N, M, V)
print(len(result))
print(*result)


(n, m) = map(int, input().split())
peer = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	peer[a].append(b)
	peer[b].append(a)
	if i == 0:
		dot0 = [a]
		dot1 = [b]
seen = [0 for _ in range(n)]
seen[dot0[0]] = 1
seen[dot1[0]] = 1
now0 = peer[dot0[0]]
while now0:
	x = now0.pop()
	if seen[x] == 0:
		seen[x] = 1
		dot0.append(x)
		now0 = peer[x]
now1 = peer[dot1[0]]
while now1:
	x = now1.pop()
	if seen[x] == 0:
		seen[x] = 1
		dot1.append(x)
		now1 = peer[x]
dot0.reverse()
dot = dot0 + dot1
print(len(dot))
print(' '.join(map(lambda x: str(x + 1), dot)))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
checked = [False] * N
checked[0] = True

def dfs(stack):
	while True:
		p = stack[-1]
		update = False
		for np in graph[p]:
			if not checked[np]:
				update = True
				stack.append(np)
				checked[np] = True
				break
		if not update:
			break
	return stack
stack1 = dfs([0])
stack2 = dfs([0])
ans = stack1[::-1] + stack2[1:]
print(len(ans))
print(' '.join([str(a + 1) for a in ans]))


(n, m) = map(int, input().split())
g = [[] for i in range(1 + n)]
v = [0] * (1 + n)
for i in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
v[a] = v[b] = 1

def dfs(p):
	path = []
	while p:
		c = p.pop()
		path.append(c)
		v[c] = 1
		flg = True
		for i in g[c]:
			if v[i] == 0:
				flg = p.append(i)
		if flg:
			return path
ans = dfs([a])[::-1] + dfs([b])
print(len(ans))
print(*ans)


def main():
	from collections import deque
	(n, m, *AB) = map(int, open(0).read().split())
	g = [[] for _ in range(n + 1)]
	(s, t) = AB[:2]
	for (a, b) in zip(*[iter(AB)] * 2):
		g[a] += [b]
		g[b] += [a]
	vis = [0] * (n + 1)
	vis[s] = vis[t] = 1
	c = 2
	ans = deque([s, t])

	def f(s, f):
		nonlocal c
		q = [s]
		while q:
			cur = q.pop()
			for nxt in g[cur]:
				if not vis[nxt]:
					q += [nxt]
					vis[nxt] = 1
					c += 1
					f(nxt)
					break
	f(s, ans.appendleft)
	f(t, ans.append)
	print(c)
	print(*ans)
main()


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = map(int, input().split())
E = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	E[a].append(b)
	E[b].append(a)
q = deque([0])
Visited = [False] * n
Visited[0] = True
while True:
	s = q[0]
	for v in E[s]:
		if not Visited[v]:
			Visited[v] = True
			q.appendleft(v)
			break
	else:
		break
while True:
	g = q[-1]
	for v in E[g]:
		if not Visited[v]:
			Visited[v] = True
			q.append(v)
			break
	else:
		break
print(len(q))
print(*list(map(lambda x: x + 1, q)))


(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
s = [0, g[0][0]]
d = [1] * n
(d[0], d[g[0][0]]) = (0, 0)
edges = [(0, g[0][0])]
inv = [0] * n
(inv[0], inv[g[0][0]]) = (1, 1)
path = [[] for _ in range(n)]
path[0].append(g[0][0])
path[g[0][0]].append(0)
while s:
	p = s.pop()
	for node in g[p]:
		if d[node]:
			s.append(node)
			d[node] = 0
			path[p].append(node)
			path[node].append(p)
			inv[p] += 1
			inv[node] += 1
			break
d = [1] * n
for i in range(n):
	if inv[i] == 1:
		s = [i]
		d[i] = 0
		break
l = [i + 1]
while s:
	p = s.pop()
	for node in path[p]:
		if d[node]:
			s.append(node)
			d[node] = 0
			l.append(node + 1)
print(len(l))
print(' '.join(map(str, l)))


(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	g[x].append(y)
	g[y].append(x)
path = [g[0][0]]
pathr = [0]
setpath = set([0, g[0][0]])
while True:
	flg = True
	for nv in g[path[-1]]:
		if nv not in setpath:
			flg = False
			path.append(nv)
			setpath.add(nv)
			break
	for nv in g[pathr[-1]]:
		if nv not in setpath:
			flg = False
			pathr.append(nv)
			setpath.add(nv)
			break
	if flg:
		break
print(len(path) + len(pathr))
pathr.reverse()
pathr += path
path = [str(pi + 1) for pi in pathr]
print(' '.join(path))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
	return int(input())

def getList():
	return list(map(int, input().split()))
import math
from collections import deque
(n, m) = getList()
vtxs = [[] for i in range(n)]
included = [0 for i in range(n)]
for i in range(m):
	(a, b) = getList()
	vtxs[a - 1].append(b - 1)
	vtxs[b - 1].append(a - 1)
q = deque()
q.append(0)
included[0] = 1
tgt = 0
flag = True
while flag:
	flag = False
	for vx in vtxs[tgt]:
		if included[vx] == 0:
			tgt = vx
			q.append(tgt)
			included[tgt] = 1
			flag = True
			break
tgt = 0
flag = True
while flag:
	flag = False
	for vx in vtxs[tgt]:
		if included[vx] == 0:
			tgt = vx
			q.appendleft(tgt)
			included[tgt] = 1
			flag = True
			break
print(len(list(q)))
print(*[i + 1 for i in list(q)])


from collections import deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
path = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	path[a - 1].append(b - 1)
	path[b - 1].append(a - 1)
l = deque()
s = set()
l.append(0)
s.add(0)
while True:
	for i in path[l[0]]:
		if not i in s:
			l.appendleft(i)
			s.add(i)
			break
	else:
		break
while True:
	for i in path[l[-1]]:
		if not i in s:
			l.append(i)
			s.add(i)
			break
	else:
		break
print(len(l))
l = list(map(lambda x: x + 1, l))
print(*l)


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
used = [0] * N
Q1 = []
Q2 = []

def dfs(v, Q):
	if used[v]:
		return 0
	used[v] = 1
	Q.append(v + 1)
	for w in G[v]:
		if dfs(w, Q):
			return 1
	return 1
if len(G[0]) == 1:
	dfs(0, Q1)
	print(len(Q1))
	print(*Q1)
else:
	used[0] = 1
	for v in G[0]:
		if dfs(v, Q1):
			break
	for v in G[0]:
		if dfs(v, Q2):
			break
	print(len(Q1) + len(Q2) + 1)
	print(*Q1[::-1] + [1] + Q2)


def main():
	from collections import deque
	(n, m) = map(int, input().split())
	ab = [list(map(int, input().split())) for _ in [0] * m]
	g = [[] for _ in [0] * n]
	[g[a - 1].append(b - 1) for (a, b) in ab]
	[g[b - 1].append(a - 1) for (a, b) in ab]
	visit = [False] * n
	visit[0] = True
	now_front = 0
	now_back = 0
	d = deque([1])
	while now_front + now_back > -2:
		if now_front != -1:
			for i in g[now_front]:
				if visit[i] == False:
					visit[i] = True
					now_front = i
					deque.appendleft(d, i + 1)
					break
			else:
				now_front = -1
		if now_back != -1:
			for i in g[now_back]:
				if visit[i] == False:
					visit[i] = True
					now_back = i
					deque.append(d, i + 1)
					break
			else:
				now_back = -1
	print(len(d))
	print(*d)
main()


def dfs():
	ans = []
	vNow = 0
	while True:
		useds[vNow] = True
		ans.append(vNow + 1)
		for v2 in adjL[vNow]:
			if not useds[v2]:
				vNow = v2
				break
		else:
			break
	return ans
(N, M) = map(int, input().split())
adjL = [[] for v in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	adjL[a - 1].append(b - 1)
	adjL[b - 1].append(a - 1)
useds = [False] * N
ans1 = dfs()
ans2 = dfs()
print(len(ans1) + len(ans2) - 1)
print(' '.join(map(str, ans1[::-1] + ans2[1:])))


from collections import deque
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
	if i == 0:
		ans = [a, b]
v = [0] * n
v[ans[0]] = 1
v[ans[1]] = 1

def check(s):
	for i in g[s]:
		if v[i] == 0:
			return i
	return -1
while True:
	a = check(ans[-1])
	if a == -1:
		break
	else:
		ans.append(a)
		v[a] = 1
ans.reverse()
while True:
	a = check(ans[-1])
	if a == -1:
		break
	else:
		ans.append(a)
		v[a] = 1
print(len(ans))
for i in range(len(ans)):
	ans[i] += 1
print(*ans)


from collections import deque
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = info[i]
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
start = 0
visited = [False] * n
visited[start] = True
li = [0]
q = deque([start])
while True:
	pos = q.pop()
	for next_pos in graph[pos]:
		if not visited[next_pos]:
			visited[next_pos] = True
			q.append(next_pos)
			li.append(next_pos)
			break
	else:
		break
li2 = []
q = deque([start])
while True:
	pos = q.pop()
	for next_pos in graph[pos]:
		if not visited[next_pos]:
			visited[next_pos] = True
			q.append(next_pos)
			li2.append(next_pos)
			break
	else:
		break
for i in range(len(li)):
	li[i] += 1
for i in range(len(li2)):
	li2[i] += 1
print(len(li) + len(li2))
print(*li[::-1] + li2)


import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7

def II():
	return int(input())

def ILI():
	return list(map(int, input().split()))

def IAI(LINE):
	return [ILI() for __ in range(LINE)]

def IDI():
	return {key: value for (key, value) in ILI()}

def solve(N, graph):
	used = [False] * (N + 1)
	used[1] = True
	right = []
	left = []
	next_node = 1
	while True:
		for node in graph[next_node]:
			if used[node] == False:
				used[node] = True
				next_node = node
				right.append(node)
				break
		else:
			break
	next_node = 1
	while True:
		for node in graph[next_node]:
			if used[node] == False:
				used[node] = True
				next_node = node
				left.append(node)
				break
		else:
			break
	ans = left[::-1] + [1] + right
	ans = list(map(str, ans))
	return ans

def main():
	(N, M) = ILI()
	graph = [[] for __ in range(N + 1)]
	for __ in range(M):
		(A, B) = ILI()
		graph[A].append(B)
		graph[B].append(A)
	ans = solve(N, graph)
	print(len(ans))
	print(' '.join(ans))
main()


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
INF = float('inf')

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]
mod = 998244353
(n, m) = LI()
graph = [[] for _ in range(n)]
for (a, b) in LIR(m):
	graph[a - 1] += [b - 1]
	graph[b - 1] += [a - 1]
visited = [0] * n
que = deque([0])
visited[0] = 1
ans = deque([0])
while que:
	cur = que.pop()
	for nxt in graph[cur]:
		if visited[nxt]:
			continue
		else:
			que += [nxt]
			ans += [nxt]
			visited[nxt] = 1
			break
que = deque([0])
while que:
	cur = que.pop()
	for nxt in graph[cur]:
		if visited[nxt]:
			continue
		else:
			que += [nxt]
			ans.appendleft(nxt)
			visited[nxt] = 1
			break
print(len(ans))
print(*[i + 1 for i in ans])


import sys
sys.setrecursionlimit(10 ** 6)

def inpl():
	return map(int, input().split())
(N, M) = inpl()
G = [[] for _ in range(N + 1)]
for _ in range(M):
	(a, b) = inpl()
	G[a].append(b)
	G[b].append(a)
searched = [False] * (N + 1)
m = 1
searched[m] = True
ans = []

def dfs(c):
	global ans
	searched[c] = True
	for d in G[c]:
		if not searched[d]:
			ans.append(c)
			dfs(d)
			break
	else:
		ans.append(c)
dfs(1)
ans = ans[:0:-1]
dfs(1)
print(len(ans))
print(*ans)


(n, m) = map(int, input().split())
s = [[] for i in range(n + 1)]
t = [1] * (n + 1)
for i in range(m):
	(a, b) = map(int, input().split())
	s[a].append(b)
	s[b].append(a)
(a, b) = ([], [])
p = 1
t[1] = 0
while 1:
	for i in s[p]:
		if t[i]:
			t[i] = 0
			p = i
			a.append(i)
			break
	else:
		break
p = 1
while 1:
	for i in s[p]:
		if t[i]:
			t[i] = 0
			p = i
			b.append(i)
			break
	else:
		break
print(1 + len(a) + len(b))
t = a[::-1] + [1] + b
print(*t)


temp = input().split()
N = int(temp[0])
M = int(temp[1])
AB = [[int(j) - 1 for j in input().split()] for i in range(M)]
chain = [[] for i in range(N)]
used = [False for i in range(N)]
ans = []
for i in range(M):
	chain[AB[i][0]].append(AB[i][1])
	chain[AB[i][1]].append(AB[i][0])
start = 0
while len(chain[start]) == 0:
	start += 1
ans.append(start)
used[start] = True
next = start
while True:
	for point in chain[next]:
		if used[point] == False:
			break
	else:
		break
	used[point] = True
	next = point
	ans.append(point)
while True:
	for point in chain[start]:
		if used[point] == False:
			break
	else:
		break
	used[point] = True
	start = point
	ans.insert(0, start)
print(len(ans))
ANS = ''
for i in ans:
	ANS += str(i + 1) + ' '
print(ANS[:-1])


import sys
input = sys.stdin.readline
inf = float('inf')
(n, m) = map(int, input().split())
edge = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	edge[b].append(a)

def f(x):
	for e in edge[x]:
		if used[e]:
			continue
		else:
			return e
	return -1
used = [False] * (n + 1)
used[1] = used[edge[1][0]] = True
path = [1, edge[1][0]]
while True:
	con = f(path[-1])
	if con == -1:
		break
	else:
		path.append(con)
		used[con] = True
path = path[::-1]
while True:
	con = f(path[-1])
	if con == -1:
		break
	else:
		path.append(con)
		used[con] = True
print(len(path))
for e in path:
	print(e, end=' ')


(N, M) = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
used = [False] * N
used[0] = used[adj[0][0]] = True
start = [0]
goal = [adj[0][0]]
while True:
	for node in adj[start[-1]]:
		if not used[node]:
			start.append(node)
			used[node] = True
			break
	else:
		break
while True:
	for node in adj[goal[-1]]:
		if not used[node]:
			goal.append(node)
			used[node] = True
			break
	else:
		break
ans = start[::-1] + goal
print(len(ans))
print(*[elem + 1 for elem in ans])


(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
ans = []
(l, r) = (0, g[0][0])
ans.append(l)
ans.append(r)
used = [l == i or r == i for i in range(n)]
(end_l, end_r) = (False, False)
while True:
	if not end_l:
		nxt = -1
		for i in g[l]:
			if used[i]:
				continue
			used[i] = True
			nxt = i
			ans.insert(0, nxt)
			l = nxt
			break
		if nxt == -1:
			end_l = True
	if not end_r:
		nxt = -1
		for i in g[r]:
			if used[i]:
				continue
			used[i] = True
			nxt = i
			ans.append(nxt)
			r = nxt
			break
		if nxt == -1:
			end_r = True
	if end_l and end_r:
		break
print(len(ans))
for i in ans:
	print(i + 1, end=' ')
print()


(n, m) = map(int, input().split())
e = [[] for _ in range(n + 1)]
for _ in range(m):
	(ai, bi) = map(int, input().split())
	e[ai].append(bi)
	e[bi].append(ai)
from collections import deque
pth = deque([1, e[1][0]])
used = [0] * (n + 1)
used[1] = 1
used[e[1][0]] = 1
for _ in range(n * 2):
	r = pth[-1]
	for v in e[r]:
		if not used[v]:
			pth.append(v)
			used[v] = 1
			break
	l = pth[0]
	for v in e[l]:
		if not used[v]:
			pth.appendleft(v)
			used[v] = 1
			break
print(len(pth))
print(*pth)


import sys
sys.setrecursionlimit(1000000)
I = lambda : map(int, input().split())
(n, m) = I()
g = [set() for _ in range(n + 1)]
v = [1 for _ in range(n + 1)]
v[1] = 0
for _ in range(m):
	(a, b) = I()
	g[a].add(b)
	g[b].add(a)

def dfs(x):
	for j in g[x]:
		if v[j]:
			v[j] = 0
			l = dfs(j)
			l.append(j)
			return l
			break
	else:
		return []
z = dfs(1) + [1] + dfs(1)[::-1]
print(len(z))
print(*z)


(N, M) = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
c = [[] for i in range(N)]
for (a, b) in AB:
	c[a - 1].append(b - 1)
	c[b - 1].append(a - 1)
v = [0] * N

def f(v, x):
	p = x
	r = [x + 1]
	while 1:
		f = 0
		for n in c[p]:
			if v[n] == 0:
				v[n] = 1
				r.append(n + 1)
				f = 1
				break
		if f == 0:
			break
		p = n
	return r
(a, b) = AB[0]
v[a - 1] = v[b - 1] = 1
r = f(v, a - 1)[::-1] + f(v, b - 1)
print(len(r))
print(*r)


from collections import deque
(N, M) = map(int, input().split())
G = [set() for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].add(b)
	G[b].add(a)
q = deque([])
q.append(0)
used = [0 for i in range(N)]
used[0] = 1
while True:
	flag = 0
	a = q[0]
	for p in G[a]:
		if used[p] == 0:
			q.appendleft(p)
			used[p] = 1
			flag = 1
			break
	b = q[-1]
	for p in G[b]:
		if used[p] == 0:
			q.append(p)
			used[p] = 1
			flag = 1
			break
	if flag == 0:
		break
ans = [str(i + 1) for i in q]
print(len(ans))
print(' '.join(ans))


from collections import deque
(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
X = [0 for i in range(N)]
q = deque([])
q.append(0)
q.append(G[0][0])
X[0] = 1
X[G[0][0]] = 1
while True:
	r = q[0]
	flag = 0
	for p in G[r]:
		if X[p] == 0:
			q.appendleft(p)
			X[p] = 1
			flag = 1
			break
	if flag == 1:
		continue
	r = q[-1]
	flag = 0
	for p in G[r]:
		if X[p] == 0:
			q.append(p)
			X[p] = 1
			flag = 1
			break
	if flag == 0:
		break
L = [str(i + 1) for i in q]
print(len(L))
print(' '.join(L))


def inpl():
	return [int(i) for i in input().split()]

def next(v):
	for i in edge[v]:
		if visited[i]:
			continue
		visited[i] = True
		return i
	return -1
from collections import defaultdict
edge = defaultdict(lambda : [])
(N, M) = inpl()
visited = [False for _ in range(N + 1)]
visited[1] = True
for _ in range(M):
	(A, B) = inpl()
	edge[A].append(B)
	edge[B].append(A)
v = 1
nv = 1
path = [1]
while nv >= 0:
	nv = next(v)
	path.append(nv)
	v = nv
path.pop()
path = list(reversed(path))
v = 1
nv = 1
while nv >= 0:
	nv = next(v)
	path.append(nv)
	v = nv
path.pop()
print(len(path))
print(*path)


(N, M, *L) = map(int, open(0).read().split())
dic = [[] for i in range(N + 1)]
for (a, b) in zip(*[iter(L)] * 2):
	dic[a].append(b)
	dic[b].append(a)
used = [False] * (N + 1)
used[1] = True
q = [1]
ans1 = []
while q:
	p = q.pop()
	ans1.append(p)
	for v in dic[p]:
		if not used[v]:
			used[v] = True
			q.append(v)
			break
q = [1]
ans2 = []
while q:
	p = q.pop()
	ans2.append(p)
	for v in dic[p]:
		if not used[v]:
			used[v] = True
			q.append(v)
			break
print(len(ans1) + len(ans2) - 1)
print(' '.join(map(str, ans1[::-1] + ans2[1:])))


(N, M) = map(int, input().split())
end = [False] * N
ans = []
dic = {}
for i in range(M):
	(A, B) = map(int, input().split())
	A -= 1
	B -= 1
	if A not in dic:
		dic[A] = []
	if B not in dic:
		dic[B] = []
	dic[A].append(B)
	dic[B].append(A)
now = 0
end[0] = True
ans.append(1)
while True:
	f = True
	for i in dic[now]:
		if not end[i]:
			end[i] = True
			now = i
			ans.append(i + 1)
			f = False
			break
	if f:
		break
now = 0
end[0] = True
ans.reverse()
while True:
	f = True
	for i in dic[now]:
		if not end[i]:
			end[i] = True
			now = i
			ans.append(i + 1)
			f = False
			break
	if f:
		break
print(len(ans))
print(' '.join(map(str, ans)))


import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def sol():
	(N, M) = map(int, input().split())
	edges = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		edges[a].append(b)
		edges[b].append(a)
	path = deque([0])
	visited = [False] * N
	visited[0] = True
	for _ in range(N - 1):
		for to in edges[path[-1]]:
			if not visited[to]:
				path.append(to)
				visited[to] = True
				break
		for leaf in edges[path[-1]]:
			if not visited[leaf]:
				break
		else:
			break
	for _ in range(N - 1):
		for to in edges[path[0]]:
			if not visited[to]:
				path.appendleft(to)
				visited[to] = True
				break
		for leaf in edges[path[0]]:
			if not visited[leaf]:
				break
		else:
			break
	print(len(path))
	ans = [p + 1 for p in path]
	print(*ans)
sol()


from collections import deque

def makePath():
	que = deque([1])
	while que:
		x = que.pop()
		for y in G[x]:
			if hist[y] == 0:
				que.append(y)
				A.append(y)
				hist[y] = 1
				break
(N, M) = map(int, input().split())
G = {i: [] for i in range(1, N + 1)}
for _ in range(M):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
A = [1]
hist = [0 for _ in range(N + 1)]
hist[1] = 1
makePath()
B = A[:]
A = []
makePath()
A = A[::-1]
A += B
print(len(A))
print(*A)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
from collections import defaultdict
(n, m) = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	ns[u].add(v)
	ns[v].add(u)
s = 0
for t in ns[s]:
	break
l = set([s, t])
from queue import deque
ans = deque([s, t])
while True:
	if not all((u in l for u in ns[s])):
		for u in ns[s]:
			if u not in l:
				break
		ans.appendleft(u)
		l.add(u)
		s = u
	elif not all((v in l for v in ns[t])):
		for v in ns[t]:
			if v not in l:
				break
		ans.append(v)
		l.add(v)
		t = v
	else:
		break
print(len(ans))
write(' '.join(map(lambda x: str(x + 1), ans)))


def examA():
	N = I()
	A = LI()
	ans = 1
	flag = None
	for i in range(N - 1):
		cur = A[i + 1] - A[i]
		if not flag:
			if cur < 0:
				flag = 'd'
			elif cur > 0:
				flag = 'u'
		elif cur < 0 and flag == 'u':
			flag = None
			ans += 1
		elif cur > 0 and flag == 'd':
			flag = None
			ans += 1
	print(ans)
	return

def examB():

	def bfs(n, V):
		W = [inf] * n
		W[0] = 0
		que = deque()
		que.append(0)
		while que:
			now = que.popleft()
			nowW = W[now]
			if nowW == 0:
				judge = 0
			elif nowW > 0:
				judge = 1
			else:
				judge = -1
			if judge < 0:
				cur = -1
			else:
				cur = 1
			for ne in V[now]:
				if cur + 1 < judge:
					break
				if W[ne] != inf:
					continue
				W[ne] = nowW + cur
				que.append(ne)
				cur -= 2
		return W
	(N, M) = LI()
	V = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = LI()
		a -= 1
		b -= 1
		V[a].append(b)
		V[b].append(a)
	L = bfs(N, V)
	D = defaultdict(int)
	minA = 0
	maxA = 0
	for (i, a) in enumerate(L, start=1):
		if a != inf:
			D[a] = i
			if a < minA:
				minA = a
			if a > maxA:
				maxA = a
	ans = []
	for i in range(minA, maxA + 1):
		ans.append(D[i])
	print(len(ans))
	print(' '.join(map(str, ans)))
	return

def examC():
	(N, L, T) = LI()
	X = [LI() for _ in range(N)]
	ans = []
	for i in range(N):
		now = T if X[i][1] == 1 else -T
		cur = (X[i][0] + now) % L
		cur = (cur + L) % L
		ans.append(cur)
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math, random
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
examB()


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
	from collections import defaultdict, deque
	(N, M) = map(int, readline().split())
	edge = defaultdict(list)
	for _ in range(M):
		(a, b) = map(int, readline().split())
		edge[a].append(b)
		edge[b].append(a)
	first = 1
	second = edge[1][0]
	visited = [False] * (N + 1)
	visited[first] = True
	visited[second] = True
	que = deque()
	que.append(first)
	path1 = []
	path2 = []
	flag = True
	while flag:
		u = que.popleft()
		path1.append(u)
		flag = False
		for v in edge[u]:
			if not visited[v]:
				visited[v] = True
				que.append(v)
				flag = True
				break
	que = deque()
	que.append(second)
	flag = True
	while flag:
		u = que.popleft()
		path2.append(u)
		flag = False
		for v in edge[u]:
			if not visited[v]:
				visited[v] = True
				que.append(v)
				flag = True
				break
	print(len(path1) + len(path2))
	print(*path1[::-1], *path2)
main()


import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
ni = lambda : int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda : list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda : float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda : list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda : stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda : stdin.readline().split()
from collections import deque

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self._size = [1 for _ in range(n)]
		self._edges = 0

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self._size[y] += self._size[x]
			self._edges += 1
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self._size[x] += self._size[y]
			self._edges += 1

	def size(self, x):
		x = self.find(x)
		return self._size[x]

	def trees(self):
		return self.n - self._edges

	def same(self, x, y):
		return self.find(x) == self.find(y)
(n, m) = na()
ab = nan(m)
g = [[] for _ in range(n)]
for i in range(m):
	(a, b) = ab[i]
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
(p, q) = ab[0]
p -= 1
q -= 1
uf = UnionFind(n)
uf.unite(p, q)
path = deque()
path.append(p)
path.append(q)
length = 2
while True:
	for i in g[p]:
		if not uf.same(p, i):
			uf.unite(p, i)
			path.appendleft(i)
			p = i
			length += 1
			break
	else:
		break
while True:
	for i in g[q]:
		if not uf.same(q, i):
			uf.unite(q, i)
			path.append(i)
			q = i
			length += 1
			break
	else:
		break
l = list(path)
print(length)
print(*[i + 1 for i in l])


from queue import deque
(n, m) = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	links[a].add(b)
	links[b].add(a)
s = 1
path = deque([s])
visited = {s}
while True:
	s_remains = links[s] - visited
	if s_remains:
		s = s_remains.pop()
		path.appendleft(s)
		visited.add(s)
	else:
		break
t = 1
while True:
	t_remains = links[t] - visited
	if t_remains:
		t = t_remains.pop()
		path.append(t)
		visited.add(t)
	else:
		break
print(len(path))
print(*path)


(N, M) = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
	(A, B) = map(int, input().split())
	edge[A - 1].append(B - 1)
	edge[B - 1].append(A - 1)
S = set()
S.add(0)
S.add(edge[0][0])
now = 0
ans1 = [1]
while True:
	next_v = -1
	for v in edge[now]:
		if v not in S:
			next_v = v
	if next_v < 0:
		break
	now = next_v
	S.add(now)
	ans1.append(now + 1)
now = edge[0][0]
ans2 = [edge[0][0] + 1]
while True:
	next_v = -1
	for v in edge[now]:
		if v not in S:
			next_v = v
	if next_v < 0:
		break
	now = next_v
	S.add(now)
	ans2.append(now + 1)
ans = ans1[::-1] + ans2
print(len(ans))
print(*ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
	tmp = list(map(int, input().split()))
	link[tmp[0] - 1].append(tmp[1] - 1)
	link[tmp[1] - 1].append(tmp[0] - 1)
from collections import deque
Q = deque()
Q.append(0)
visited = [-1] * n
hist = deque()
while Q:
	now = Q.pop()
	if visited[now] != -1:
		continue
	hist.append(now + 1)
	visited[now] = 0
	is_nxt = False
	for nxt in link[now]:
		if visited[nxt] == -1:
			is_nxt = True
			Q.append(nxt)
	if not is_nxt:
		break
Q = deque()
Q.append(0)
visited[0] = -1
while Q:
	now = Q.pop()
	if visited[now] != -1:
		continue
	if now != 0:
		hist.appendleft(now + 1)
	visited[now] = 0
	is_nxt = False
	for nxt in link[now]:
		if visited[nxt] == -1:
			is_nxt = True
			Q.append(nxt)
	if not is_nxt:
		break
print(len(hist))
print(*hist, sep=' ')


from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input = lambda : sys.stdin.readline().rstrip()
(N, M) = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
data = [[] for i in range(N + 1)]
for (a, b) in AB:
	data[a].append(b)
	data[b].append(a)
a = 1
b = data[a][0]
visited = {a, b}
lst = []
for z in [a, b]:
	stack = [z]
	while 1:
		a = stack[-1]
		for p in data[a]:
			if not p in visited:
				stack.append(p)
				visited.add(p)
				break
		else:
			break
	lst.append(stack)
lst[0].reverse()
lst[0] += lst[1]
print(len(lst[0]))
print(' '.join([str(i) for i in lst[0]]))


(N, M) = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	X[a - 1].append(b - 1)
	X[b - 1].append(a - 1)
(l, r) = (a - 1, b - 1)
(L, R) = ([l], [r])
D = [0] * N
D[l] = D[r] = 1
while True:
	for x in X[l]:
		if D[x] == 0:
			D[x] = 1
			l = x
			L.append(x)
			break
	else:
		break
while True:
	for x in X[r]:
		if D[x] == 0:
			D[x] = 1
			r = x
			R.append(x)
			break
	else:
		break
print(len(L + R))
print(*[a + 1 for a in L[::-1] + R])


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint

def ceil(a, b):
	return (a + b - 1) // b
inf = float('inf')
mod = 10 ** 9 + 7

def pprint(*A):
	for a in A:
		print(*a, sep='\n')

def INT_(n):
	return int(n) - 1

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def MI_():
	return map(INT_, input().split())

def LI():
	return list(MI())

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return list(MF())

def LIN(n: int):
	return [I() for _ in range(n)]

def LLIN(n: int):
	return [LI() for _ in range(n)]

def LLIN_(n: int):
	return [LI_() for _ in range(n)]

def LLI():
	return [list(map(int, l.split())) for l in input()]

def I():
	return int(input())

def F():
	return float(input())

def ST():
	return input().replace('\n', '')

def main():
	(N, M) = MI()
	edge = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = MI_()
		edge[a].append(b)
		edge[b].append(a)
	path = deque([0, edge[0][0]])
	in_path = [False] * N
	in_path[0] = True
	in_path[edge[0][0]] = True
	while len(path) < N:
		added = False
		for to in edge[path[0]]:
			if not in_path[to]:
				path.appendleft(to)
				added = True
				in_path[to] = True
				break
		if added:
			continue
		for to in edge[path[-1]]:
			if not in_path[to]:
				path.append(to)
				in_path[to] = True
				added = True
				break
		if not added:
			break
	print(len(path))
	print(*[p + 1 for p in path])
main()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
	(A, B) = map(int, input().split())
	G[A].append(B)
	G[B].append(A)
visited = [False] * (N + 1)
visited[1] = True
path = []
v = 1
while True:
	path.append(v)
	for c in G[v]:
		if not visited[c]:
			v = c
			visited[v] = True
			break
	else:
		break
path = path[::-1]
path.pop()
v = 1
while True:
	path.append(v)
	for c in G[v]:
		if not visited[c]:
			v = c
			visited[v] = True
			break
	else:
		break
print(len(path))
print(*path)


(n, m) = map(int, input().split())
C = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
	for j in range(2):
		C[i][j] -= 1
s0 = C[0][0]
s1 = C[0][1]
M = [[] for i in range(n)]
for i in range(m):
	M[C[i][0]].append(C[i][1])
	M[C[i][1]].append(C[i][0])
V = [0] * n
V[s0] = 1
V[s1] = 1
ng = 0
s = s0
S0 = [s0]
while ng == 0:
	ng = 1
	for i in M[s]:
		if V[i] == 0:
			V[i] = 1
			ng = 0
			s = i
			S0.append(i)
			break
s = s1
S1 = [s1]
ng = 0
while ng == 0:
	ng = 1
	for i in M[s]:
		if V[i] == 0:
			V[i] = 1
			ng = 0
			s = i
			S1.append(i)
			break
ANS = S1[::-1] + S0
for i in range(len(ANS)):
	ANS[i] += 1
print(len(ANS))
print(*ANS)


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
(n, m) = inm()
dst = [{} for i in range(n + 1)]
for i in range(m):
	(a, b) = inm()
	dst[a][b] = dst[b][a] = 1
used = [False] * (n + 1)
v = 1
used[v] = True
a = []
b = []
while True:
	found = False
	for u in dst[v]:
		if used[u]:
			continue
		used[u] = True
		a.append(u)
		found = True
		v = u
		break
	if not found:
		break
v = 1
while True:
	found = False
	for u in dst[v]:
		if used[u]:
			continue
		used[u] = True
		b.append(u)
		found = True
		v = u
		break
	if not found:
		break
b.reverse()
b.append(1)
b.extend(a)
print(len(b))
print(*b)


(N, M) = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
V = [0] * N
V[0] = 1
P1 = []
P2 = []
s = 0

def pathfind(s):
	P = []
	for _ in range(N):
		P.append(str(s + 1))
		for t in E[s]:
			if V[t]:
				continue
			s = t
			V[t] = 1
			break
		else:
			break
	return P
P1 = pathfind(0)
P2 = pathfind(0)
P = P1[len(P1):0:-1] + P2
print(len(P))
print(' '.join(P))


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float('inf')

def main():
	(N, M) = map(int, input().split())
	graph = defaultdict(list)
	for _ in range(M):
		(A, B) = map(int, input().split())
		graph[A].append(B)
		graph[B].append(A)
	route = deque()
	used = set()
	route.appendleft(1)
	used.add(1)
	for n in graph[1]:
		route.append(n)
		used.add(n)
		break
	while True:
		(start, end) = (route[0], route[-1])
		start_ok = True
		for n in graph[start]:
			if n not in used:
				start_ok = False
				route.appendleft(n)
				used.add(n)
				break
		end_ok = True
		for n in graph[end]:
			if n not in used:
				end_ok = False
				route.append(n)
				used.add(n)
				break
		if start_ok and end_ok:
			break
	print(len(route))
	print(*route, sep=' ')
main()


(n, m) = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
ans = [a + 1, b + 1]
visited = {a, b}
s = b
while 1:
	flag = True
	for i in edge[s]:
		if i in visited:
			continue
		visited.add(i)
		flag = False
		ans.append(i + 1)
		s = i
		break
	if flag:
		break
ans = ans[::-1]
s = a
while 1:
	flag = True
	for i in edge[s]:
		if i in visited:
			continue
		visited.add(i)
		flag = False
		ans.append(i + 1)
		s = i
		break
	if flag:
		break
print(len(ans))
print(*ans)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for i in range(1 + n)]
v = [0] * (1 + n)
for i in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
	if i == 0:
		q = [a, b]
		v[a] = v[b] = 1
p = [q[-1]]
path = []
while p:
	cur = p.pop()
	path.append(cur)
	v[cur] = 1
	flg = True
	for i in g[cur]:
		if v[i] == 0:
			p.append(i)
			flg = False
	if flg:
		break
ans = path
p = [q[0]]
path = []
while p:
	cur = p.pop()
	path.append(cur)
	v[cur] = 1
	flg = True
	for i in g[cur]:
		if v[i] == 0:
			p.append(i)
			flg = False
	if flg:
		break
ans = path[::-1] + ans
print(len(ans))
print(*ans)


import sys
input = sys.stdin.readline
from collections import deque
(N, M) = map(int, input().split())
table = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	table[a].append(b)
	table[b].append(a)
H = deque()
H.append(0)
S = set()
S.add(0)
flag = True
while flag:
	flag = False
	x = H[-1]
	for a in table[x]:
		if a not in S:
			flag = True
			S.add(a)
			H.append(a)
			break
flag = True
while flag:
	flag = False
	x = H[0]
	for a in table[x]:
		if a not in S:
			flag = True
			S.add(a)
			H.appendleft(a)
			break
print(len(H))
print(' '.join(map(str, [h + 1 for h in H])))


(N, M) = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
	(A, B) = map(int, input().split())
	G[A].append(B)
	G[B].append(A)
check = [0] * (N + 1)
check[1] = 1
ans1 = [1]
stack = [1]
while stack:
	tmp = stack.pop()
	for next_ in G[tmp]:
		if check[next_] == 1:
			continue
		else:
			stack.append(next_)
			check[next_] = 1
			ans1.append(next_)
			break
ans2 = []
stack = [1]
while stack:
	tmp = stack.pop()
	for next_ in G[tmp]:
		if check[next_] == 1:
			continue
		else:
			stack.append(next_)
			check[next_] = 1
			ans2.append(next_)
			break
print(len(ans1) + len(ans2))
print(*ans2[::-1], end='')
if len(ans1):
	print(' ', end='')
else:
	print()
print(*ans1)