Xiao Jia has recently become fascinated with being a tour guide, spending all day thinking about taking tourists to visit various attractions. As M City is hosting the NOI, there are many visitors. Many friends have introduced people in need of a tour guide to Xiao Jia.
M City has $n$ famous attractions, which Xiao Jia has numbered from $1$ to $n$. There are bidirectional roads between some attractions. Xiao Jia can have tourists gather at any attraction, then lead them on a tour, and finally end the tour at any attraction. However, the visiting tourists do not want to go to places they have already visited. Therefore, Xiao Jia cannot take the tourists through the same attraction twice or more.
Xiao Jia hopes you can help him design a plan, find a feasible route, and take the tourists to visit as many places as possible.
Input
The input files are guide1.in through guide10.in. The first line contains two integers $n$ and $m$, representing the number of attractions and the number of roads, respectively. The following $m$ lines each contain two integers $a$ and $b$, representing a bidirectional road between attraction $a$ and attraction $b$.
Output
You need to output your answers to guide1.out through guide10.out, where guide?.out is the answer corresponding to guide?.in. The first line of the output should contain $p$, the number of attractions visited along the path you found. The next $p$ lines each contain an integer, representing each attraction on the path in order.
Note
This is an answer-submission problem. You do not need to provide any source code; you only need to place your output files in the same directory as the *.in files.
Examples
Input 1
5 5 1 2 3 2 2 4 2 5 4 5
Output 1
4 1 2 4 5
Note 1
The problem may have multiple solutions. This example has 4 solutions; you only need to output any one of them.
| Solution 1 | Solution 2 | Solution 3 | Solution 4 |
|---|---|---|---|
| 4 | 4 | 4 | 4 |
| 1 | 1 | 3 | 3 |
| 2 | 2 | 2 | 2 |
| 4 | 5 | 4 | 5 |
| 5 | 4 | 5 | 4 |
Scoring
Your score will be determined by the difference between your answer and the standard answer. Let $x$ be the number of attractions visited in your correct answer, and let $ans$ be the result we provide. Your score is calculated according to the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 12 | $x > ans$ | 5 | $x \ge ans \times 0.93$ |
| 10 | $x = ans$ | 4 | $x \ge ans \times 0.9$ |
| 9 | $x \ge ans - 1$ | 3 | $x \ge ans \times 0.8$ |
| 8 | $x \ge ans - 2$ | 2 | $x \ge ans \times 0.7$ |
| 7 | $x \ge ans - 3$ | 1 | $x \ge ans \times 0.5$ |
| 6 | $x \ge ans \times 0.95$ | 0 | $x < ans \times 0.5$ |
If multiple conditions are met, the highest score among the satisfied conditions will be taken.