# KOITST 21 Railroad

https://www.acmicpc.net/problem/22029

**This is a communication problem**

Country B has a railway network, and Country A is trying to gather intelligence on it. The following is known about the network:

* The railway network consists of $N$ stations, each numbered from 1 to $N$, and $N-1$ railways
* It is possible to travel from any station to any other station using the railways

Country A decides to bribe a high-ranking official from Country B's railway company to obtain a drawing of the railway network. To avoid exposing the traitor, the official will alter the drawing before sending it to Country A by doing the following three step procedure:

1. Draw $K$ fake railways on the map
2. Mark a single station by drawing a square around it
3. Remove all station numbers from the railway network

For example, consider the following railway network with $N=6$ stations and we are tasked to draw $K=1$ fake railways:


The following is a possible way to alter the network:

**Step 1.** draw $K=1$ fake railways: between station $2$ and $4$


**Step 2.** Mark station $1$ by drawing a square around it


**Step 3.** Remove all station numbers


The railway network after 3 steps is what country A will receive, and they must determine which are the $N-1$ original railways (the black, solid lines in the above diagram).

## Implementation

You need to 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 in Country B's railway network. All stations are represented by integers between $1$ and $N$ inclusive.
* The integer `K` given as an argument represents the number of fake railways to be added.
* `X` is an argument to record the number of the station with the special mark. When the function terminates, `X` should hold a positive integer between 1 and $N$ inclusive.
* The array `E` has a size of $N-1$. `E` represents Country B's railway network, where a pair $(a, b)$ stored in E means that station $a$ and station $b$ are directly connected by a railway.
* This function returns an array of $K$ pairs $(a, b)$, representing fake railways directly connecting two distinct stations $a$ and $b$. Two stations $a$ and $b$ that are already connected by a real or fake railway cannot be connected again by a fake railway.

`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 in Country B's railway network. All stations are represented by integers between $1$ and $N$ inclusive.
* 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 with the special mark.
* The array `E` has a size of $N + K - 1$. `E `represents the drawing sent to Country A, where a pair $(a, b)$ stored in E means that station $a$ and station $b$ are directly connected by a real or fake railway.
* This function reconstructs the original railway network from the drawing created by the encode_map function. It returns an array of $N-1$ pairs $(a, b)$, representing Country B's original railway network.

Afer `encode_map` is run, the method in which the parameters for `decode_map` is generated is as follows:

1. The array `E` is formed by the $N-1$ original railways and $K$ fake railways
2. `E` is shuffled at random
3. A random permutation $P$ of $1$ to $N$, is generated. Then, each edge `(a,b)` in `E` will be replaced by `(P[a], P[b])`. `X` will also be replaced by `P[X]`. This step corresponds to the removal of the station numbers.

In the submitted source code, no input/output should be executed at any part.

Each test case includes one or more independent scenarios.

### How the code is executed

For a test case containing $T$ scenarios, the program calls the above functions exactly twice in the following manner:

First Execution:
* The encode_map function is called $T$ times.
* The results of the encode_map function calls are stored in the grading system.
* The decode_map function is not called.

Second Execution:
* The decode_map function is called multiple times. For each call, a random scenario is chosen, and the drawing created by the encode_map function in this scenario is used as input for the decode_map function.
* The encode_map function is not called.

The program's execution time and memory usage are measured across both executions.

## Constraints

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

## Subtasks

* Subtask 1 (4 points): $N \le 4$
* Subtask 2 (13 points): $K = 1$
* Subtask 3 (11 points): Each station is connected to at most two railways.
* Subtask 4 (29 points): Any station can reach any other station through at most $\lfloor \frac{N}{2} \rfloor$ railways.
* Subtask 5 (43 points): No additional constraints.

### Scoring Criteria

You will score points only if you create a correct drawing in the encode_map function and correctly reconstruct the railway network in the decode_map function. Specifically, if the array returned by the `decode_map` function includes 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 is not important

# Example

Consider the case where $N = 6$, $K = 1$, and the railways $E = [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)]$. This corresponds on the example above

The grader will call the following function:

encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])


Next, the grader will call the following function. Note that the order of railways in the last array may vary, and that the station numbers have been renumbered according to a random permutation. In particular, the permutation is $[2,3,4,5,6,1]$.

decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])

The input represents the following diagram. Note that the station numbers differ from those used in the `encode_map` function.


This function returns `[(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)]`. The order of elements may vary.

This example satisfies the conditions of subtasks 2, 4, and 5.