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

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

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

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

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

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


if __name__ == "__main__":
    main()

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

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

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

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

Solution (Python):

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


if __name__ == "__main__":
    B()

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

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

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

ans = deque()
ans.append(1)
seen = [False] * (N + 1)
seen[1] = True
v = 1
ok = True
while ok:
    ok = False
    for u in graph[v]:
        if not seen[u]:
            ans.append(u)
            seen[u] = True
            v = u
            ok = True
            break
v = 1
ok = True
while ok:
    ok = False
    for u in graph[v]:
        if not seen[u]:
            ans.appendleft(u)
            seen[u] = True
            v = u
            ok = True
            break
print(len(ans))
print(*ans)

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

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a].append(b)
    es[b].append(a)
path = [[], []]
used = [0] * (N+1)
used[1] = 1
for i in range(2):
    dq = deque()
    dq.append(1)
    while len(dq):
        v = dq.popleft()
        for u in es[v]:
            if used[u] == 0:
                used[u] = 1
                dq.append(u)
                path[i].append(u)
                break
path = path[0][::-1] + [1] + path[1]
print(len(path))
print(*path)

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

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

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

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

ANS=str(ans[0])
for i in range(1,len(ans)):
    ANS+=" "+str(ans[i])
print(len(ans))
print(ANS)

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

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

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

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

ans=dfs([a])[::-1]+dfs([b])
print(len(ans))
print(*ans)

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

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

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

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

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

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

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 = [], []

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

Solution (Python):


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

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

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

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

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

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

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