Description

Xiao Jia recently became obsessed with being a tour guide and keeps thinking about taking tourists to visit various scenic spots. It so happens that NOI is being held in M City, and there are many visitors. Many friends introduced people who need a tour guide to Xiao Jia.

There are $n$ famous scenic spots in M City, numbered from $1$ to $n$. Some pairs of scenic spots are connected by bidirectional roads. Xiao Jia can gather the tourists at any scenic spot to start the tour and can also end the tour at any scenic spot. However, the tourists do not want to visit a place they have already visited. Therefore, Xiao Jia cannot pass through the same scenic spot more than once.

Xiao Jia hopes you can help design a plan: choose a feasible route that visits as many scenic spots as possible.

Input Format

The input files are guide1.in ~ guide10.in. The first line contains two integers $n, m$, the number of scenic spots and the number of roads. The next $m$ lines each contain two integers $a, b$, indicating there is a bidirectional road between scenic spot $a$ and scenic spot $b$.

Output Format

You need to write the answers to guide1.out ~ guide10.out, where guide?.out is the answer corresponding to guide?.in. The first line outputs $p$, the number of scenic spots on your path. Then output $p$ lines, each containing one integer, in order, representing each scenic spot on your path.

5 5
1 2
3 2
2 4
2 5
4 5

4
1
2
4
5

Hint

[Explanation] This is an output-only problem. You do not need to submit any source code; just place your output files in the same directory as the corresponding *.in files.

[Sample Explanation] The problem may have multiple correct answers. This sample has 4 solutions. You only need to output any one of them.

::cute-table{tuack}

[Scoring Method] Your score is determined by the difference between your answer and the official answer. Suppose your answer is correct and the number of scenic spots visited is $x$, and our result is $\mathit{ans}$. Then your score is computed as follows:

::cute-table{tuack}

If multiple conditions are satisfied, take the highest score.

Translated by ChatGPT 5