There are two countries, A and B, that are on bad terms. Country A wants to find out the railway network of Country B to invade it.

Although Country A has sent several spies to Country B, they were always caught before they could gather meaningful information, so the following is all the information Country A has:

• Country B's railway network consists of $N$ stations, and each station is numbered from 1 to $N$.
• Any two different stations are connected either directly by a railway or through other station(s) connected by railways.
• For any two stations, there is exactly one path connecting them.
• There is no case where a station is directly connected to itself by a railway.

Realizing the limitations of sending spies, Country A decides to bribe a high-ranking official of Country B's railway company to obtain a drawing of the railway network. Since sending this drawing directly would reveal the identity of the traitor, the traitor will modify the drawing and send it to Country A as follows:

• Draw $K$ fake railways on the drawing of the railway network. That is, choose two different stations $a$ and $b$ that are not directly connected by a railway in the drawing, and connect them directly with a fake railway. Repeat this $K$ times.
• Place a special mark on one station.
• Finally, erase all the station numbers.

The traitor sends the final drawing to Country A. Since it is difficult to know that this is a drawing of Country B's railway network from this information alone, no one will know that secret information has been leaked.

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

• The drawing received by Country A has the station numbers erased, and it is not indicated which railways are real and which are fake. All that is known is which station has a special mark, and the fact that a total of $K$ fake railways were placed.
• Therefore, the sender must place fake railways in appropriate locations and place a special mark on an appropriate station so that the receiver can distinguish which railways are real and which are fake just by looking at the drawing.
• Also, the receiver must understand how the sender modified the drawing and obtain the original railway network drawing from the received drawing.

As described above, two functions are needed: one that modifies the drawing of the railway network, and one that obtains the real railway network from this drawing. Country A intends to entrust this task to you.

Implementation Details

You must implement the following two functions:

vector< pair<int, int> > encode_map(int N, int K, int &X, vector< pair<int, int> > E)

• The integer $N$ given as an argument represents the number of stations $N$ in Country B's railway network. All stations are represented by integers from 1 to $N$.
• The integer $K$ given as an argument represents the number of fake railways to add.
• $X$ is an argument to record the number of the station to be specially marked. When the function terminates, $X$ must store a positive integer between 1 and $N$.
• The size of the array $E$ given as an argument is $N - 1$. $E$ represents Country B's railway network, and the fact that the pair $(a, b)$ is stored in $E$ means that station $a$ and station $b$ are directly connected by a railway.
• This function returns an array containing $K$ pairs $(a, b)$, which means connecting two different stations $a$ and $b$ with a fake railway. Whether real or fake, you cannot connect two stations $a$ and $b$ that are already connected by a railway with a fake railway again.

vector< pair<int, int> > decode_map(int N, int K, int X, vector< pair<int, int> > E)

• The integer $N$ given as an argument represents the number of stations $N$ in Country B's railway network. All stations are represented by integers from 1 to $N$. Since the station numbers were all erased during the process of sending the drawing, the station numbers used in this function may differ from the actual station numbers. That is, the station numbers used in this function are the result of calculating the station numbers used in the encode_map function through some bijection.
• The integer $K$ given as an argument represents the number of added fake railways.
• The integer $X$ given as an argument represents the number of the station that has a special mark.
• The size of the array $E$ given as an argument is $N + K - 1$. $E$ represents the drawing delivered to Country A, and the fact that the pair $(a, b)$ is stored in $E$ means that station $a$ and station $b$ are directly connected by a real/fake railway in the drawing. Note that the order of elements in $E$ has no meaning.
• This function plays the role of restoring the original drawing from the drawing created by the encode_map function. That is, this function returns an array containing $N - 1$ pairs $(a, b)$, which must contain Country B's railway network.

You must not execute input/output functions in any part of the submitted source code.

Each test case contains one or more independent scenarios. For a single test case containing $T$ scenarios, the program calling the above functions is executed exactly twice as follows.

When the program is executed for the first time: The encode_map function is called $T$ times. The execution results of the encode_map function are stored in the grading system. * The decode_map function is not called.

When the program is executed for the second time: The decode_map function is called multiple times. In each call, an arbitrary scenario is selected, and the drawing created by the encode_map function in this scenario is used as the input for the decode_map function. The encode_map function is not called.

In this problem, the program's execution time and memory usage are calculated by combining the two executions.

Constraints

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

Subtasks

1. (4 points)
   • $N \le 4$
2. (13 points)
   • $K = 1$
3. (11 points)
   • Each station is connected to at most two railways.
4. (29 points)
   • One can move from any station to any other station by passing through at most $\frac{N}{2}$ railways.
5. (43 points)
   • No additional constraints.

Note

The data is considered correct only if the encode_map function creates a correct drawing and the decode_map function accurately identifies the railway network. In particular, if the array returned by the decode_map function contains even one fake railway, the score for that data is 0. The order of elements in the arrays returned by the encode_map and decode_map functions does not matter.

Note that the score for each subtask is the minimum of the scores for all data in that subtask.

Examples

Input 1

(Example input data for the sample grader)

Output 1

(Example output data for the sample grader)

Figure 1. The left drawing represents Country B's railway network. If you add a fake railway (4, 2) and place a special mark on station 1, you can obtain the right drawing.

Sample grader

The sample grader receives input in the following format:

• Line 1: $T$

Following this, $T$ blocks representing each scenario follow. Each block has the following format:

• Line 1: $N$ $K$
• Line $1 + i$ ($1 \le i \le N - 1$): $a_i$ $b_i$

The pair $a_i, b_i$ means that a railway exists connecting station $a_i$ and station $b_i$.

The sample grader outputs the following for each scenario:

• Line 1: The array returned by the encode_map function
• Line 2: The array returned by the decode_map function

Note that the sample grader may differ from the actual grader used for scoring.