Jenna is playing a computer game involving a large map with cities numbered sequentially from to that are connected by bidirectional roads. The game's objective is to travel to as many cities as possible without visiting any city more than once. The more cities the player visits, the more points they earn.
As Jenna's fellow student at Hackerland University, she asks you for help choosing an optimal path. Given the map, can you help her find a path that maximizes her score?
Note: She can start and end her path at any two distinct cities.
Input Format
The first line contains two space-separated integers describing the respective values of (the number of cities) and (the number of roads).
Each line of the subsequent lines contains two space-separated integers, and , describing a bidirectional road between cities and .
Map Generation Algorithm
The graph representing the map was generated randomly in the following way:
- Initially, the graph was empty.
- Permutations were chosen uniformly at random among all permutations.
- For each , edge was added to the graph.
- An additional edges were chosen uniformly at random among all possible sets of edges which don't intersect with edges added during step .
Constraints
- For of test and .
- For of test and .
- For of test and .
- It's guaranteed that a valid path of length always exists.
Scoring
- A valid path of length earns of a test case's available points. The total score will be rounded to next .
Output Format
Print the following two lines of output:
- The first line must contain a single integer, , denoting the length of the path.
- The second line must contain distinct space-separated integers describing Jenna's path in the same order in which she visited each city.
Sample Input 0
4 5
3 1
3 4
2 4
2 3
4 1
Sample Output 0
4
1 4 2 3
Explanation 0
The diagrams below depict the city's initial map, an optimal path that would earn a full score, and an alternative path that would earn a partial score:
In the optimal path (center image), Jenna walks the path . This answer earns of the maximum score because the path length, , is equal to (i.e., she was able to visit every city exactly once).
In the alternative path (right image), Jenna walks the path for of the maximum score.