A. Kowloon Walled City
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the North of the modern-day Kowloon Island, there lies the memorial park of the historic Kowloon Walled City. Once a military fort and enclave of the Qing Dynasty, it became lawless in 1899 after diplomatic conflicts between the Qing and the British government. Its lawless status has persisted throughout most of the 20th century, until its demolishment in 1994. Over the years, the Kowloon Walled City become one of the most densely populated place in the world.

Kowloon Walled City (© City of Darkness Revisited)
Hand-drawn Map (© Kowloon Walled City Kaifong Welfare Promotion Association)

Now, imagine you are given the map of the bygone Kowloon Walled City. The map can be considered as a connected, undirected graph with $$$N$$$ locations and $$$M$$$ pathways. There might exist multiple pathways between the same two locations.

Initially, you start in location $$$1$$$. Each step, if there are pathways remaining for the location you are in, you can choose any one of them and move to the other side of the pathway. Then, you cross out that pathway on the map. If at any moment, there are no more pathways on the map attached to the location you are in, you are stuck.

Your target is to construct moves that lead to you being stuck at some location other than location $$$1$$$. Report if no such sequence of moves exists.

Input

The first line contains two integers: $$$N, M$$$ ($$$2 \leq N \leq 10^5, N - 1 \leq M \leq 2 \times 10^5$$$), the number of locations and the number of pathways, respectively. The $$$i^\text{th}$$$ line among the next $$$M$$$ lines contains two integers: $$$U_i, V_i$$$ ($$$1 \leq U_i \neq V_i \leq N$$$), meaning that there is an undirected pathway between location $$$U_i$$$ and location $$$V_i$$$.

Output

If such a walk exists, then on the first line, output $$$K$$$ ($$$2 \leq K \leq M + 1$$$), the length of the walk. Then, on the next line, output $$$K$$$ integers: $$$S_1, S_2, \dots, S_K$$$, where $$$S_1 = 1$$$, there is a pathway between $$$S_i$$$ and $$$S_{i+1}$$$ for $$$1 \leq i \leq K - 1$$$, and you are stuck at $$$S_K$$$ afterwards.

Otherwise, if no such walk exists, output -1 on the first and only line.

If there exists multiple walks that make you stuck at locations other than location $$$1$$$, you may output any of them.

Examples
Input
4 4
1 2
2 3
3 4
4 1
Output
-1
Input
6 8
1 2
2 3
3 4
5 4
6 5
2 5
4 5
1 6
Output
8
1 6 5 4 3 2 5 4
Note

Sample 1:

You will always go back to location 1 no matter how you walk.

Sample 2:

The walk 1 6 5 4 3 2 5 is not accepted. Although you do not go back to location 1, you haven't got stuck yet.