Mind Swap Problem#3178
In a famous mathematical problem inspired by a Futurama episode, several people have swapped minds using a mind-swapping machine. The machine has one important limitation: any two people can swap minds with each other at most once.
After some number of swaps have occurred, everyone wants to return to their original body. However, since each pair can only swap once, direct reversal is impossible. The solution requires using at most two additional "helper" bodies that haven't participated in any swaps yet.
Given the history of swaps that have already occurred, determine a sequence of additional swaps to return everyone to their original body.
The first line contains numbers (2 \leq n \leq 200) — the number of people, and (1 \leq m \leq \frac{n(n-1)}{2}) — the number of swaps that have already occurred. The next lines describe the swaps. Bodies are numbered from to . Each swap is represented by two numbers , (1 \leq a, b \leq n) — the numbers of the bodies involved in the swap. Swaps are listed in chronological order.
In the first line, print the number of swaps needed to return everyone to their own body. Then print the swaps themselves, in the order they should be performed, one swap per line in the same format as the input. Any valid sequence of swaps may be output, but no more than two extra bodies may be used. Extra bodies should be numbered n+1 and n+2. After all swaps, the extra bodies must also be in their original state. The total number of swaps in your solution should not exceed .
Beispiel 1