Kingpin Escape#9888
You are the kingpin of a large criminal network. Your hideouts are connected by underground passageways in such a way that there is exactly one route between any two hideouts. Your headquarters is located in hideout .
The police are going to block the passageways one at a time. You learn about each block in advance and have enough time to move through the remaining passageways. You want to dig several new passageways so that, whichever single passageway is blocked, every hideout can still reach the headquarters. Find the minimum number of new passageways and specify which passageways should be dug.
The first line contains two integers n~(2 \le n \le 10^5) and h~(0 \le h < n) — the number of hideouts and the number of the hideout where the headquarters is located. The hideouts are numbered from to n - 1.
Each of the next n - 1 lines contains two integers and b~(0 \le a, b < n) — the numbers of hideouts connected by a passageway.
In the first line print an integer — the minimum number of new passageways.
In each of the next lines print two integers and — the numbers of hideouts to be connected by a new passageway. If there are several solutions, print any of them.
Example 1
Example 2