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

Solution (Python):
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

L = [[] for _ in range(N)]

for a, b in AB:
  a -= 1
  b -= 1
  L[a].append(b)
  L[b].append(a)

D = [False] * N
D[0] = True
t = 0
Ans = [1]
while True:
  for x in L[t]:
    if not D[x]:
      t = x
      D[x] = True
      Ans.append(x + 1)
      break
  else:
    break

t = 0
Ans = Ans[::-1]

while True:
  for x in L[t]:
    if not D[x]:
      t = x
      D[x] = True
      Ans.append(x + 1)
      break
  else:
    break

print(len(Ans))
print(" ".join(list(map(str, Ans))))

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

start=0
spath={0}
path=[0]
todo=[0]
next=g[0].pop()
spath.add(next)
path.append(next)
while g[path[-1]]:
  next=g[path[-1]].pop()
  if next not in spath:
    spath.add(next)
    path.append(next)
rpath=[0]
while g[rpath[-1]]:
  next=g[rpath[-1]].pop()
  if next not in spath:
    spath.add(next)
    rpath.append(next)
rpath.reverse()
rpath.pop()
rpath+=path
rpath=[i+1 for i in rpath]
print(len(rpath))
print(*rpath,sep=' ')

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

start=0
spath={0}
path=[0]
todo=[0]
next=g[0].pop()
spath.add(next)
path.append(next)
while g[path[-1]]-spath:
  next=g[path[-1]].pop()
  if next not in spath:
    spath.add(next)
    path.append(next)
rpath=[0]
while g[rpath[-1]]-spath:
  next=g[rpath[-1]].pop()
  if next not in spath:
    spath.add(next)
    rpath.append(next)
rpath.reverse()
rpath.pop()
rpath+=path
rpath=[i+1 for i in rpath]
print(len(rpath))
print(*rpath,sep=' ')

Solution (Python):
from collections import defaultdict, deque


def main():
    N, M = list(map(int, input().split()))
    adj = defaultdict(list)
    A, B = -1, -1
    for _ in range(M):
        A, B = list(map(lambda x: int(x) - 1, input().split()))
        adj[A].append(B)
        adj[B].append(A)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

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


def main():
    from collections import defaultdict, deque

    N, M = map(int, readline().split())

    edge = defaultdict(list)

    for _ in range(M):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    first = 1
    second = edge[1][0]

    visited = [False] * (N + 1)
    visited[first] = True
    visited[second] = True

    que = deque()
    que.append(first)

    path1 = []
    path2 = []

    flag = True

    while flag:
        u = que.popleft()
        path1.append(u)
        flag = False
        for v in edge[u]:
            if not visited[v]:
                visited[v] = True
                que.append(v)
                flag = True
                break

    que = deque()
    que.append(second)
    flag = True

    while flag:
        u = que.popleft()
        path2.append(u)
        flag = False
        for v in edge[u]:
            if not visited[v]:
                visited[v] = True
                que.append(v)
                flag = True
                break

    print(len(path1) + len(path2))
    print(*path1[::-1], *path2)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

from collections import deque
q = deque([0, es[0][0]])
st = set([0, es[0][0]])

while 1:
    a,b = q[0],q[-1]
    for to in es[a]:
        if to in st: continue
        st.add(to)
        q.appendleft(to)
        break
    else:
        for to in es[b]:
            if to in st: continue
            st.add(to)
            q.append(to)
            break
        else:
            print(len(q))
            print(*[a+1 for a in q])
            exit()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)

l = deque([1])
s = set([1])
while True:
    check = True
    for nex in e[l[-1]]:
        if nex in s:
            continue
        l.append(nex)
        s.add(nex)
        check = False
        break
    if check:
        break
while True:
    check = True
    for nex in e[l[0]]:
        if nex in s:
            continue
        l.appendleft(nex)
        s.add(nex)
        check = False
        break
    if check:
        print(len(l))
        print(*l)
        exit()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)

l = deque([1])
visit = [0]*(n+1)
visit[1] = 1
while True:
    check = True
    for nex in e[l[-1]]:
        if visit[nex]:
            continue
        l.append(nex)
        visit[nex] = 1
        check = False
        break
    if check:
        break
while True:
    check = True
    for nex in e[l[0]]:
        if visit[nex]:
            continue
        l.appendleft(nex)
        visit[nex] = 1
        check = False
        break
    if check:
        print(len(l))
        print(*l)
        exit()

Solution (Python):
from collections import deque

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

l = deque([1])
visit = [0]*(n+1)
visit[1] = 1
while True:
    check = True
    for nex in e[l[-1]]:
        if visit[nex]:
            continue
        l.append(nex)
        visit[nex] = 1
        check = False
        break
    if check:
        break
while True:
    check = True
    for nex in e[l[0]]:
        if visit[nex]:
            continue
        l.appendleft(nex)
        visit[nex] = 1
        check = False
        break
    if check:
        print(len(l))
        print(*l)
        exit()

Solution (Python):
from collections import deque

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

l = deque([1])
s = set([1])
while True:
    check = True
    for nex in e[l[-1]]:
        if nex in s:
            continue
        l.append(nex)
        s.add(nex)
        check = False
        break
    if check:
        break
while True:
    check = True
    for nex in e[l[0]]:
        if nex in s:
            continue
        l.appendleft(nex)
        s.add(nex)
        check = False
        break
    if check:
        print(len(l))
        print(*l)
        exit()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
data = list(map(int,read().split()))

links = [set() for _ in range(n+1)]
it = iter(data)
for a,b in zip(it,it):
    links[a].add(b)
    links[b].add(a)

ans = [1]
done = [0] * (n+1)
done[1] = 1
now = 1
while(links[now]):
    i = links[now].pop()
    if(done[i]==1):
        continue
    done[i] = 1
    ans.append(i)
    now = i

ans = ans[::-1]
now = 1
while(links[now]):
    i = links[now].pop()
    if(done[i]==1):
        continue
    done[i] = 1
    ans.append(i)
    now = i
    
print(len(ans))
print(' '.join(map(str,ans)))

Solution (Python):

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

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



def solve(N,edges):
    adj = [[] for _ in range(N)]
    for a,b in edges:
        adj[a].append(b)
        adj[b].append(a)

    visited = [False]*N

    right = []
    v = 0
    visited[v] = True
    while True:
        for u in adj[v]:
            if not visited[u]:
                right.append(u)
                v = u
                visited[v] = True
                break
        else:
            break

    left = []
    v = 0
    while True:
        for u in adj[v]:
            if not visited[u]:
                left.append(u)
                v = u
                visited[v] = True
                break
        else:
            break

    left.reverse()
    return left+[0]+right



if __name__ == '__main__':
    N,M = map(int,readline().split())
    m = map(lambda x: int(x)-1, read().split())

    path = solve(N,zip(m,m))
    print(len(path))
    print(*(v+1 for v in path))

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

Solution (Python):
from collections import deque
N, M = map(int, input().split())

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


seen = [0] * (N + 1)
seen[1] = 1
ans = deque([1])


s = 1
while True:
    update = False
    for t in edge[s]:
        if seen[t]:
            continue
        update = True
        seen[t] = 1
        break
    if not update:
        break
    ans.append(t)
    s = t

s = 1
while True:
    update = False
    for t in edge[s]:
        if seen[t]:
            continue
        update = True
        seen[t] = 1
        break
    if not update:
        break
    ans.appendleft(t)
    s = t

print(len(ans))
print(*ans)

Solution (Python):
N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

used = [False] * N
used[0] = used[adj[0][0]] = True
start = [0]
goal = [adj[0][0]]

while True:
    for node in adj[start[-1]]:
        if not used[node]:
            start.append(node)
            used[node] = True
            break
    else:
        break

while True:
    for node in adj[goal[-1]]:
        if not used[node]:
            goal.append(node)
            used[node] = True
            break
    else:
        break

ans = start[::-1] + goal
print(len(ans))
print(*[elem + 1 for elem in ans])

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

Solution (Python):
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  x,y=x-1,y-1
  g[x].append(y)
  g[y].append(x)

path=[g[0][0]]
pathr=[0]

setpath=set([0,g[0][0]])
while True:
  flg=True
  for nv in g[path[-1]]:
    if nv not in setpath:
      flg=False
      path.append(nv)
      setpath.add(nv)
      break
  for nv in g[pathr[-1]]:
    if nv not in setpath:
      flg=False
      pathr.append(nv)
      setpath.add(nv)
      break
  if flg:break

print(len(path)+len(pathr))
pathr.reverse()
pathr+=path
path=[str(pi+1) for pi in pathr]
print(' '.join(path))

Solution (Python):

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


def ddprint(x):
  if DBG:
    print(x)

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

Solution (Python):
from collections import deque

class Graph(): 
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)
            self.graph[e[1] - indexed].append(e[0] - indexed)
            self.deg[e[0] - indexed] += 1
            self.deg[e[1] - indexed] += 1

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, E)
used = [0 for _ in range(N)]

res = deque([E[0][0], E[0][1]])
used[res[0] - 1] = 1
used[res[-1] - 1] = 1

flag_lt = True
flag_rt = True
while flag_lt or flag_rt:
    lt = res[0] - 1
    rt = res[-1] - 1
    if flag_lt:
        for adj in g.graph[lt]:
            if not used[adj]:
                used[adj] = 1
                res.appendleft(adj + 1)
                break
        else:
            flag_lt = False
    if flag_rt:
        for adj in g.graph[rt]:
            if not used[adj]:
                used[adj] = 1
                res.append(adj + 1)
                break
        else:
            flag_rt = False

print(len(res))
print(*res)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
s = 0
for t in ns[s]:
    break
l = set([s,t])
from queue import deque
ans = deque([s,t])
while True:
    if not all(u in l for u in ns[s]):
        for u in ns[s]:
            if u not in l:
                break
        ans.appendleft(u)
        l.add(u)
        s = u
    elif not all(v in l for v in ns[t]):
        for v in ns[t]:
            if v not in l:
                break
        ans.append(v)
        l.add(v)
        t = v
    else:
        break
print(len(ans))
write(" ".join(map(lambda x: str(x+1), ans)))

Solution (Python):
import sys

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

def graph_input(N, M):
    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    return G

N, M = map(int, readline().split())
G = graph_input(N, M)



visited = [0] * (N + 1)
a = 1
b = G[a][0]
Pa = [a]
Pb = [b]
visited[a] = 1
visited[b] = 1
while True:
    v = Pa[-1]
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        Pa.append(w)
        break
    if v == Pa[-1]:
        break
while True:
    v = Pb[-1]
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        Pb.append(w)
        break
    if v == Pb[-1]:
        break

P = Pa[::-1] + Pb
print(len(P))
print(*P)

Solution (Python):
n,m=map(int, input().split())
e=[[] for _ in range(n+1)]
for _ in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi);e[bi].append(ai)

from collections import deque

pth=deque([1,e[1][0]])
used=[0]*(n+1)
used[1]=1;used[e[1][0]]=1

for _ in range(n*2):
    r=pth[-1]
    for v in e[r]:
        if not used[v]:
            pth.append(v)
            used[v]=1
            break
    l=pth[0]
    for v in e[l]:
        if not used[v]:
            pth.appendleft(v)
            used[v]=1
            break
print(len(pth))
print(*pth)

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)
used = [False]*(N+1)
used[1] = True
q = [1]
ans1 = []
while q:
  p = q.pop()
  ans1.append(p)
  for v in dic[p]:
    if not used[v]:
      used[v] = True
      q.append(v)
      break
q = [1]
ans2 = []
while q:
  p = q.pop()
  ans2.append(p)
  for v in dic[p]:
    if not used[v]:
      used[v] = True
      q.append(v)
      break
print(len(ans1)+len(ans2)-1)
print(' '.join(map(str,(ans1[::-1]+ans2[1:]))))

Solution (Python):
import sys




from collections import deque

input=sys.stdin.readline

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

Solution (Python):
import sys
input = sys.stdin.readline

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

Solution (Python):
N,M=map(int,input().split())
edge=[set([]) for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    edge[a-1].add(b-1)
    edge[b-1].add(a-1)

visit=set([0])
ans=[0]
pos=0
while True:
    for i in edge[pos]:
        if i not in visit:
            ans.append(i)
            visit.add(i)
            pos=i
            break
    else:
        break

ans=ans[::-1]
pos=ans[-1]
while True:
    for i in edge[pos]:
        if i not in visit:
            ans.append(i)
            visit.add(i)
            pos=i
            break
    else:
        break

for i in range(len(ans)):
    ans[i]+=1

print(len(ans))
print(*ans)

Solution (Python):
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

s0 = C[0][0]
s1 = C[0][1]

M = [[] for i in range(n)]
for i in range(m):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])


V = [0] * n
V[s0] = 1
V[s1] = 1



ng = 0
s = s0
S0 = [s0]
while ng == 0:
    ng = 1
    for i in M[s]:
        if V[i] == 0:
            V[i] = 1
            ng = 0
            s = i
            S0.append(i)
            break


s = s1
S1 = [s1]
ng = 0
while ng == 0:
    ng = 1
    
    for i in M[s]:
        if V[i] == 0:
            V[i] = 1
            ng = 0
            s = i
            S1.append(i)
            break

ANS = S1[::-1] + S0
for i in range(len(ANS)):
    ANS[i] += 1
print(len(ANS))
print(*ANS)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))







def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

N,M = LI()
A,B = LIR(M,2)

pt = edges_to_pt(A,B,N)

s = 0
path1 = [s]
visited = [False]*N
visited[s] = True
S = [s]
while S:
    v = S.pop()
    for u in pt[v]:
        if not visited[u]:
            visited[u] = True
            path1.append(u)
            S.append(u)
            break

s = 0
path2 = []
S = [s]
while S:
    v = S.pop()
    for u in pt[v]:
        if not visited[u]:
            visited[u] = True
            path2.append(u)
            S.append(u)
            break

path = list(reversed(path2))+path1
path = list(map(lambda x:x+1,path))

print(len(path))
print(*path)

Solution (Python):
N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

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

add_node(1)
ans = ans[::-1]
add_node(1)

print(len(ans))
print(*ans)

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

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()

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

visited={a,b}
lst=[]
for z in [a,b]:
    stack=[z]
    while 1:
        a=stack[-1]
        for p in data[a]:
            if not p in visited:
                stack.append(p)
                visited.add(p)
                break
        else:
            break
    lst.append(stack)

lst[0].reverse()
lst[0]+=lst[1]
print(len(lst[0]))
print(" ".join([str(i) for i in lst[0]]))

Solution (Python):


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

from collections import deque

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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)

n, m = na()
ab = nan(m)

g = [[] for _ in range(n)]
for i in range(m):
    a, b = ab[i]
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

p, q = ab[0]
p -= 1
q -= 1
uf = UnionFind(n)
uf.unite(p, q)
path = deque()
path.append(p)
path.append(q)
length = 2

while True:
    for i in g[p]:
        if not uf.same(p, i):
            uf.unite(p, i)
            path.appendleft(i)
            p = i
            length += 1
            break
    else:
        break

while True:
    for i in g[q]:
        if not uf.same(q, i):
            uf.unite(q, i)
            path.append(i)
            q = i
            length += 1
            break
    else:
        break

l = list(path)
print(length)
print(*[i + 1 for i in l])

Solution (Python):

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

used = [False] * N
used[0] = used[edge[0][0]] = True
path = [0, edge[0][0]]

def not_use(v):
    """
    頂点vの隣接頂点で未使用なものを返す
    ない場合 -> -1
    """
    for e in edge[v]:
        if used[e]: continue
        else: return e
    return -1

def append():
    """
    右端に頂点を追加していく
    """
    while True:
        v = not_use(path[-1])
        if v < 0:
            break
        else:
            path.append(v)
            used[v] = True

def main():
    """
    DFS的に頂点を追加していくと、
    どこにも遷移できない頂点に行き着く
    -> それが端点
    これは条件3を満たしている
    """
    append()
    path.reverse()
    append()

    ans = [v + 1 for v in path]
    print(len(ans))
    print(*ans, sep=" ")

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
c=[1 for i in range(n+1)]
ans=[]
def f(s):
    c[s]=0
    ans.append(s)
    for i in edge[s]:
        if c[i]:
            return f(i)
f(1)
ans.reverse()
del ans[-1]
f(1)
print(len(ans))
print(" ".join(map(str,ans)))