Hipermetropie

Back when the Dacians were still fighting the samurai, in a hidden corner of the world, there existed the city of Hipermetropolis, the most technologically advanced civilization of its time. The ruler of this city, King Hip, was a man passionate about logic and games, so he had his subjects take part in various games that tested their wits.

We go back in time to a random day in the city of Hipermetropolis and find out that today's game is the following:

The King selects $N$ subjects (perfect logicians) and places them in a forest (a set of trees) with $N$ nodes and $M$ undirected edges, each subject standing at a different node. Like all inhabitants of the city of Hipermetropolis, they are farsighted (they cannot see well up close), so a subject cannot see the edges incident to their own node, but they can see all other edges and all other nodes.

At the start of the game, the King announces to all the subjects:

"The graph you are in is a forest with at least one edge."

After the subjects receive this information, the game begins. It unfolds over several rounds: at the start of a round, the king takes, one by one, the subject at node $1$, then the one at node $2$, and so on, and asks each of them, in secret: "Can you say with certainty that you have at least one edge incident to your node?", to which the subject answers with Yes or No.

NOTE: the king keeps every participant's answer secret. When a round ends, if at least one subject answered Yes, then the game ends. Otherwise, the game continues with a new round, the subjects deducing that all the answers were negative.

Implementation Details

Given the values $N$, $M$, and the $M$ edges, you must determine the round in which the game ends, as well as the subjects who answer Yes in that round.

You must implement the following function:

std::pair<int, std::vector<int>> solve(int N, std::vector<int> u, std::vector<int> v);

which receives as parameters:

• $N$, the number of nodes in the graph.
• $u$, a vector of size $M$
• $v$, a vector of size $M$

meaning that there exists an undirected edge from $u_i$ to $v_i$, $\forall \ i , 0 \leq i < M$.

The subjects may be returned in any order.

The judge will call the function exactly once for each test.

Constraints and Notes

• $1 \leq M < N \leq 500 \ 000$
• $1 \leq v_i, u_i \leq N$ and $v_i \neq u_i$, $\forall \ 0 \leq i < M$
• The graph described in the input is a forest. In other words, it has no cycles.
• The subjects are perfect logicians and know that all the others are perfect logicians as well.
• A perfect logician is defined as follows: if they have enough information to deduce $X$, they will deduce $X$.
• A subject will never lie and will answer Yes as soon as possible.
• It can be proven that the game ends after a finite number of rounds.
• The subjects know the rules of the game.
• All subjects accept the king's statement as true.
• The first round is round $1$.

Example 1

input

3 2
1 2
1 3

output

1
1

Explanation

Subject $1$ sees no edge in the graph and deduces that there must be at least one edge incident to him, which makes him answer Yes in the first round. The other two subjects answer No to the king's question because they each see another edge.

Example 2

input

4 2
1 2
3 4

output

2
1 2 3 4

Explanation

In the first round, each subject sees one edge, so everyone answers No. In the second round, subject $1$ reasons as follows: "In the first round, subject $3$ saw an edge, but he is incident to the only edge I see: edge $(3, 4)$, an edge that subject $3$ does not see. That means he must have seen an edge that I do not see, i.e., an edge incident to me." The other $3$ subjects reason analogously, and everyone answers Yes.