Railway

Time limit1sMemory limit1024 MB

Summary

Write an encoder that adds K fake edges to a tree and marks one node, and a decoder that recovers the original tree from the altered graph.

Level: Medium7 of 10
Topics: Tree, Implementation, DFS
Solved: No attempts yet

Problem

Two countries, A and B, are on bad terms. Country A wants to invade B and is trying to learn the railway network of B. Country A has sent spies to B many times, but every spy was caught before gathering any meaningful information. So all that country A knows is the following.

The railway network of B consists of $N$ stations, numbered from $1$ to $N$ .
For any two different stations, they are connected directly by a rail or through other stations linked by rails.
For any two different stations, there is exactly one path connecting them.
No station is directly connected by a rail to itself.

Realizing the limits of sending spies, country A plans to bribe a senior executive of B's railway company to obtain a drawing of the network. Sending the drawing as is would reveal the traitor, so the traitor will alter the drawing as follows before sending it to A.

Draw $K$ fake rails on the drawing. Choose two different stations $a$ and $b$ that are not directly connected by a rail, and connect them with a fake rail. Repeat this $K$ times.
Mark one station with a special mark.
Finally, erase the numbers of all stations.

The traitor sends the final drawing to A. Since the drawing alone does not reveal that it shows B's railway network, nobody will know that the secret information has leaked.

For this plan to succeed, the following problems must be solved.

The drawing that A receives has no station numbers, and it does not indicate which rails are real and which are fake. A only knows which station has the special mark and that $K$ fake rails were added.
Therefore, the sender must add fake rails at suitable positions and place the special mark on a suitable station, so that the receiver can tell real rails from fake ones using only the drawing.
The receiver must understand how the sender altered the drawing and recover the original railway drawing from the received one.

As described above, two functions are needed: one that alters the railway drawing, and one that recovers the real railway network from the altered drawing. Country A asks you to take on this task.

Constraints

Time limit: 1000 ms. Memory limit: 1024 MB.

$1 \le T \le 200$
$3 \le N \le 200$
$1 \le K < \frac{N}{2}$

Examples1

Example 1
Input
```
1
3 1
1 2
2 3
```
Expected output
```
1 3
1
```