A 国与 B 国关系不和。A 国为了入侵 B 国，试图探明 B 国的铁路网。虽然 A 国曾多次派遣间谍，但间谍总是在获取有价值的信息前被捕，因此 A 国目前掌握的信息仅限于以下几点：
- B 国的铁路网由 $N$ 个车站组成，每个车站编号为 1 到 $N$。
- 任意两个不同的车站之间，要么有铁轨直接相连，要么可以通过其他车站间接相连。
- 任意两个车站之间，连接它们的路径有且仅有一条。
- 不存在车站与自身直接相连的情况。
A 国意识到派遣间谍存在局限性，于是决定收买 B 国铁路公司的高层，以获取绘制好的铁路网图。由于直接发送原图会暴露叛徒的身份，叛徒将按以下方式修改图纸后再发送给 A 国：
- 在铁路网图上绘制 $K$ 条假铁轨。即在图中选择两个原本没有直接连接的车站 $a$ 和 $b$，用假铁轨将它们直接相连。此过程重复 $K$ 次。
- 对其中一个车站进行特殊标记。
- 最后，擦除所有车站的编号。
叛徒将最终得到的图纸发送给 A 国。由于仅凭这些信息很难判断这就是 B 国的铁路网图，因此没有人会发现秘密信息已经泄露。
为了使该计划成功，必须解决以下问题：
- A 国收到的图纸中，车站编号已被擦除，且无法区分哪些是真铁轨，哪些是假铁轨。唯一已知的信息是哪个车站被做了特殊标记，以及总共添加了 $K$ 条假铁轨。
- 因此，发送方需要根据图纸，在适当的位置添加假铁轨，并对适当的车站进行特殊标记，以便接收方仅凭图纸就能分辨出哪些是真铁轨，哪些是假铁轨。
- 同时，接收方需要理解发送方的修改方法，并从收到的图纸中还原出原始的铁路网图。
如上所述，我们需要实现两个函数：一个用于修改铁路网图，另一个用于从修改后的图中还原出真实的铁路网。A 国希望由你来完成这项任务。
函数列表及定义
你需要实现以下两个函数：
vector< pair<int, int> > encode_map(int N, int K, int &X, vector< pair<int, int> > E)- 参数 $N$ 表示 B 国铁路网中的车站数量。所有车站用 1 到 $N$ 之间的整数表示。
- 参数 $K$ 表示要添加的假铁轨数量。
- $X$ 是用于记录特殊标记车站编号的参数。函数结束时，$X$ 必须存储一个 1 到 $N$ 之间的整数。
- 参数数组 $E$ 的大小为 $N - 1$。$E$ 表示 B 国的铁路网，序对 $(a, b)$ 存储在 $E$ 中表示车站 $a$ 和车站 $b$ 之间有铁轨直接相连。
- 该函数返回一个包含 $K$ 个序对 $(a, b)$ 的数组，表示用假铁轨连接两个不同的车站 $a$ 和 $b$。无论真假，不能将已经通过铁轨直接相连的两个车站再次用假铁轨连接。
vector< pair<int, int> > decode_map(int N, int K, int X, vector< pair<int, int> > E)- 参数 $N$ 表示 B 国铁路网中的车站数量。所有车站用 1 到 $N$ 之间的整数表示。由于在发送过程中车站编号已被擦除，该函数中使用的车站编号可能与实际编号不同。即，该函数中使用的车站编号是
encode_map函数中使用的编号经过某种双射函数计算后的结果。 - 参数 $K$ 表示添加的假铁轨数量。
- 参数 $X$ 表示被特殊标记的车站编号。
- 参数数组 $E$ 的大小为 $N + K - 1$。$E$ 表示发送给 A 国的图纸，序对 $(a, b)$ 存储在 $E$ 中表示图中车站 $a$ 和车站 $b$ 之间有真/假铁轨直接相连。注意，$E$ 中元素的顺序没有意义。
- 该函数负责从
encode_map函数生成的图中还原出原始图。即，该函数返回一个包含 $N - 1$ 个序对 $(a, b)$ 的数组，其中应存储 B 国的原始铁路网。
提交的源代码中不得包含任何输入输出函数。
每个测试用例包含一个或多个独立的场景。对于包含 $T$ 个场景的测试用例，调用上述函数的程序将准确执行两次。
程序第一次执行时：
encode_map函数被调用 $T$ 次。encode_map函数的执行结果被存储在评测系统中。decode_map函数不会被调用。
程序第二次执行时：
decode_map函数被多次调用。在每次调用中，会选择一个随机场景，该场景中由encode_map函数生成的图将作为decode_map函数的输入。encode_map函数不会被调用。
在本题中，程序的运行时间和内存使用量是两次执行的总和。
数据范围
- $1 \le T \le 200$
- $3 \le N \le 200$
- $1 \le K < \frac{N}{2}$
子任务
- (4分)
- $N \le 4$
- (13分)
- $K = 1$
- (11分)
- 每个车站连接的铁轨最多两条。
- (29分)
- 从任意车站出发，最多经过 $\frac{N}{2}$ 条铁轨即可到达其他任意车站。
- (43分)
- 无额外限制。
评分标准
只有在 encode_map 函数生成正确的图，且 decode_map 函数准确还原出铁路网的情况下，该数据才会被判定为正确。特别地，如果 decode_map 函数返回的数组中包含任何一条假铁轨，则该数据的得分为 0。encode_map 和 decode_map 函数返回的数组中，元素的顺序不重要。
请注意，每个子任务的得分是该子任务所有数据得分中的最小值。
样例
- 考虑 $N = 6, K = 1$，铁轨 $E = [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)]$ 的情况。
评测机调用以下函数：
encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])左图表示 B 国的铁路网。添加假铁轨 $(4, 2)$ 并对 1 号车站进行特殊标记，即可得到右图。在这种情况下，encode_map 函数返回 $[(4, 2)]$，且 $X$ 中存储 1。除此之外可能存在其他答案。
接下来，评测机调用以下函数。作为最后一个参数传入的数组，其元素顺序可能会发生变化。
decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])输入所表示的图如下所示。请注意，车站编号与 encode_map 函数中使用的编号不同。
该函数返回 $[(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)]$。元素顺序可以改变。该示例满足第 2、4、5 号子任务的条件。
说明
Sample grader 按以下格式接收输入：
- 第 1 行：$T$
随后是 $T$ 个块，每个块代表一个场景。每个块的格式如下：
- 第 1 行：$N \ K$
- 第 $1 + i$ 行 ($1 \le i \le N - 1$)：$a_i \ b_i$
$a_i, b_i$ 对表示 $a_i$ 号车站和 $b_i$ 号车站之间存在铁轨。
Sample grader 对每个场景按以下格式输出：
- 第 1 行：函数
encode_map返回的数组 - 第 2 行：函数
decode_map返回的数组
请注意，Sample grader 可能与实际评测时使用的评测机不同。