6780.Round Trip

Time Limit: 1s Memory Limit: 512MB

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 Format(From the terminal/stdin)

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.

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

Output Format(To the terminal/stdout)

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".

Sample Input

Copy
5 6
1 3
1 2
5 3
1 5
2 4
4 5
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n

Sample Output special judge

Copy
4
3 5 1 3
 \n
 · · · \n
Source: CSES, Graph Algorithms, 1669

Submit

请先 登录

© 2025 FAQs