Round Trip

Task:

Byteland has $n$ cities and $m$ roads between them. Your task is to design a round trip that begins in a city, goes through two or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.

Input

The first input line has two integers $n$ and $m$: the number of cities and roads. The cities are numbered $1,2,\dots,n$.

Then, there are $m$ lines describing the roads. Each line has two integers $a$ and $b$: there is a road between those cities.

Every road is between two different cities, and there is at most one road between any two cities.

Output

First print an integer $k$: the number of cities on the route. Then print $k$ cities in the order they will be visited. You can print any valid solution.

If there are no solutions, print "IMPOSSIBLE".

Constraints

• $1 \le n \le 10^5$
  
• $1 \le m \le 2 \cdot 10^5$
  
• $1 \le a,b \le n$
  

Solutions:

We can treat the cities as vertexes and the roads as edges, and at the end we have an undirected graph. The problem can restate as finding the cyclic path in undirected graph if it's existed. For detecting an existed cyclic path, It springs to mind with two approaches, the first is Union-find and the other is DFS/BFS. However, I think Union-find cant help to print the path. Hence, DFS/BFS is a most suitable way for detecting as well as printing the cyclic path.

W.L.O.G We can start at any vertex, and traveling through the graph in DFS way until reaching the visited vertex, then concluding the cyclic path is existed, otherwise It's non acyclic graph. While doing it, we keep track the state of vertex which is passed. And one more attention, Because It's undirected graph, so we need to mark the previous vertex in order to skip when considering in the children vertex of current vertex.
Implementation:

 1from collections import defaultdict
 2import sys
 3sys.setrecursionlimit(9**9)
 4def dfs(node,graph,path,pre,visited): # passing the previous vertex (pre)
 5  visited[node]=True
 6  for i in graph[node]:
 7      if i==pre: # skipping edge to previous vertex
 8          continue
 9      path.append(i)
10      if visited[i]: # intermediatly return False coz we come to visited vertex which is constructed a circle path.
11          return False
12    
13      if not dfs(i,graph,path,node,visited):
14          return False
15      path.pop()
16  return True
17
18def main():
19  n,m = map(int,input().strip().split())
20  graph=defaultdict(list) 
21
22  # constructing an undirected graph
23  for i in range(m):
24      u,v=map(int,input().strip().split())
25      graph[u].append(v)
26      graph[v].append(u)
27
28  # generating an array that tracking the state of visited vertex ( = True)
29  visited=[False]*(n+1)
30
31  # the cyclic path
32  path=[]
33  for i in range(1,n+1):
34      if not visited[i]:
35          path.append(i)
36          if not dfs(i,graph,path,0,visited):
37              break
38          path.pop()
39  if len(path)==0:
40      print("IMPOSSIBLE")
41  else:
42      first=path.index(path[-1])
43      path=path[first:]
44      print(len(path))
45      print(" ".join([str(i) for i in path]))
46  main()
47 

Time complexity: With DFS, the time complexity definitely is $O(N)$.

Space complexity: By tracking the state of vertex, so we have $O(N)$ for space complexity where N is the number of vertexes.