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):
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"
        else:
            if 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)]

if __name__ == '__main__':
    examB()

"""

"""

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

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

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

Solution (Python):
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] += [b]
  dic[b] += [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)
log = set(pre)
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(*ans)

Solution (Python):
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] += [b]
  dic[b] += [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)
log = set()
ans = []
while True:
  if pre:
    p = pre.pop()
    log.add(p)
    ans.append(p)
    continue
  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(*ans)

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

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

Solution (Python):











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])
if __name__ == '__main__':
    main()

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

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

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

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

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

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

Solution (Python):


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)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
  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)
if __name__ == "__main__":
  main()

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

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

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

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

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

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

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

if __name__=="__main__":
	main()

Solution (Python):
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
ans = deque([s, t])
q = [s]
while q:
	cur = q.pop()
	for nxt in g[cur]:
		if not vis[nxt]:
			q += [nxt]
			vis[nxt] = 1
			ans.appendleft(nxt)
			break
q = [t]
while q:
	cur = q.pop()
	for nxt in g[cur]:
		if not vis[nxt]:
			q += [nxt]
			vis[nxt] = 1
			ans.append(nxt)
			break
print(len(ans))
print(*ans)

Solution (Python):
def 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 a in E[a]:
            if not visited[a]:
                A.append(a)
                visited[a] = True
                break
        else:
            break

    B = [b]
    while True:
        for b in E[b]:
            if not visited[b]:
                B.append(b)
                visited[b] = True
                break
        else:
            break

    ans = A[::-1] + B
    print(len(ans))
    print(*ans)

main()

Solution (Python):
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 a in E[a]:
        if not visited[a]:
            A.append(a)
            visited[a] = True
            break
    else:
        break

B = [b]
while True:
    for b in E[b]:
        if not visited[b]:
            B.append(b)
            visited[b] = True
            break
    else:
        break

ans = A[::-1] + B
print(len(ans))
print(*ans)

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

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

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

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

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

Solution (Python):

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

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

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