Description

There is a TV show called "Super Hero". The general process is: each contestant goes on stage to answer several questions from the host, and receives different amounts of prizes or money based on how many questions are answered correctly. The host prepares several questions, and only when a contestant answers a question correctly can they proceed to the next one; otherwise, they are eliminated. To make the show more entertaining and slightly easier, the host provides contestants with several "lifelines", such as asking the audience or removing several wrong options (for multiple-choice questions), etc.

Here, we slightly change the rules. Suppose the host has $m$ questions in total, and the contestant has $n$ different "lifelines".

The host stipulates that for each question, you may choose one from two specified "lifelines", and each "lifeline" can be used at most once.

We also assume that once a question uses one of its allowed "lifelines", it will definitely be answered correctly, and the contestant proceeds to the next question.

Now I am on the show, but I am so bad that I cannot solve any question on my own, so I have to rely on using a "lifeline" for every question.

If I already know which two "lifelines" are available for each question, can you tell me how to choose them to pass as many questions as possible?

Input Format

The first line contains two positive integers $n, m\ (1 \le n, m \le 1000)$, indicating there are $n$ kinds of "lifelines" numbered $0 \sim n-1$, and there are $m$ questions in total.

The next $m$ lines each contain two integers, indicating the IDs of the two "lifelines" available for the $i$-th question.

Note: Each "lifeline" ID can be used at most once, but the two "lifelines" for the same question may be identical.

Output Format

Output the first line as the maximum number of questions $p$ that can be passed. Then output $p$ lines, where the $i$-th line is the ID of the "lifeline" used for the $i$-th question.

If there are multiple valid answers, output any one of them. This problem uses Special Judge.

5 6
3 2
2 0
0 3
0 4
3 2
3 2

4
3
2
0
4

Hint

Thanks to @zhouyonglong for providing the Special Judge.

Translated by ChatGPT 5