Problem:
 Score : 500 points    Problem Statement 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.        Sample Input 1 5 6
1 3
1 4
2 3
1 5
3 5
2 4      Sample Output 1 4
2 3 1 4  There are two vertices directly connected to vertex 2 : vertices 3 and 4 .
There are also two vertices directly connected to vertex 4 : vertices 1 and 2 .
Hence, the path 2 → 3 → 1 → 4 satisfies the conditions.       Sample Input 2 7 8
1 2
2 3
3 4
4 5
5 6
6 7
3 5
2 6      Sample Output 2 7
1 2 3 4 5 6 7

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)))

Solution (Python):
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)

Solution (Python):
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

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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:])))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
n, m=map(int, raw_input().split())
adj=[[] for i in range(n+1)]
for i in range(m):
	a, b=map(int, raw_input().split())
	adj[a].append(b)
	adj[b].append(a)
visited=[False]*(n+1)
def dfs(cur):
	result=[]
	while True:
		result.append(cur)
		found=False
		for to in adj[cur]:
			if not visited[to]:
				visited[to]=True
				cur=to
				found=True
				break
		if not found:
			break
	return result
for i in range(n+1):
	if adj[i]:
		to=adj[i][0]
		visited[i]=True
		visited[to]=True
		result=list(reversed(dfs(to)))+dfs(i)
		print len(result)
		for cur in result:
			print cur,
		print
		exit()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
n,m=map(int,input().split())
e=[set() for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  e[a].add(b)
  e[b].add(a)

closed_path=set()
n=1
answer=[]

while True:
  answer.append(n)
  closed_path.add(n)
  for i in e[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 e[n]:
    if i not in closed_path:
      n=i
      break
  else:
    break

print(len(answer))
print(*answer)

Solution (Python):
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=" ")

Solution (Python):

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))


if __name__ == '__main__':
    main()

Solution (Python):

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))


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
import string
import re
import datetime
import calendar
import collections
import heapq
import bisect
import array

import numpy as np
import scipy as sp

n, m = map(int, input().split())

graph = collections.defaultdict(list)

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

used = set()
s = 1
t = graph[1][0]
used.add(s)
used.add(t)
path_s = [s]
path_t = [t]

while True:
    for next in graph[s]:
        if not next in used:
            used.add(next)
            s = next
            path_s.append(s)
            break
    else:
        break

while True:
    for next in graph[t]:
        if not next in used:
            used.add(next)
            t = next
            path_t.append(t)
            break
    else:
        break

print(len(path_s)+len(path_t))

for x in path_s[::-1]:
    print(x,end=" ")
for x in path_t[:len(path_t)-1]:
    print(x,end=" ")
print(path_t[len(path_t)-1])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


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()

Solution (Python):

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)

Solution (Python):
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 = [], []


def dfs(n, ans):
    ans.append(str(n+1))
    visited.add(n)
    for ni in G[n]:
        if ni not in visited:
            dfs(ni, ans)
            break


dfs(0, ans1)
for ni in G[0]:
    if ni not in visited:
        dfs(ni, ans2)
        break

print(len(ans1) + len(ans2))
print(" ".join(ans2[::-1] + ans1))

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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))))

Solution (Python):
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=" ")


if __name__ == '__main__':
    main()

Solution (Python):
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=" ")


if __name__ == '__main__':
    main()

Solution (Python):
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())

Solution (Python):
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)

Solution (Python):
from collections import deque
from sys import setrecursionlimit
setrecursionlimit(10**6)

def dfs1(now,visited,ans):
    visited[now]=True
    for nx in g[now]:
        if not visited[nx]:
            ans.appendleft(nx)
            dfs1(nx,visited,ans)
            break

def dfs2(now,visited,ans):
    visited[now]=True
    for nx in g[now]:
        if not visited[nx]:
            ans.append(nx)
            dfs2(nx,visited,ans)
            break

n,m=map(int,raw_input().split())
g=[[] for _ in xrange(n)]
for i in xrange(m):
    a,b=map(int,raw_input().split())
    a-=1;b-=1
    g[a].append(b)
    g[b].append(a)
ans=deque([a,b])
visited=[False]*n
visited[a]=True
visited[b]=True
dfs1(a,visited,ans)
dfs2(b,visited,ans)
print len(ans)
for i in xrange(len(ans)):
    print ans[i]+1,
print

Solution (Python):

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))


if __name__ == "__main__":
    main()