题目背景

本题翻译自 2021년도 국제정보올림피아드 대표학생 선발고사 1차 선발고사 #4 철도。

受评测技术限制，本题采用交互题实现，即两个函数会在同一次运行中被调用。

提交时，请在程序开头添加如下内容，并且无需引用 railroad.h：

#include <vector>
#include <utility>

std::vector< std::pair<int, int> > encode_map(int N, int K, int &X, std::vector< std::pair<int, int> > E);
std::vector< std::pair<int, int> > decode_map(int N, int K, int X, std::vector< std::pair<int, int> > E);

警告：滥用本题评测将被封号。

题目描述

有两个关系恶劣的国家 A 和 B。A 国为了侵略 B 国，试图获取 B 国的铁路网络信息。

A 国多次派遣间谍，但总是在获取有意义的信息前被捕，因此 A 国目前掌握的信息仅有以下内容：

• B 国的铁路网络由 $N$ 个车站组成，每个车站编号为 $1$ 到 $N$。
• 任意两个不同的车站之间要么直接通过铁路相连，要么通过其他车站（一个或多个）间接相连。
• 任意两个车站之间只有唯一的一条路径相连。
• 不存在车站与自身直接相连的铁路。

意识到派遣间谍的局限性后，A 国决定收买 B 国铁路公司的高管，以获取铁路网络图。为了避免暴露叛徒身份，叛徒会对图纸进行如下修改：

1. 在铁路网络图上添加 $K$ 条假铁路。即，选择图中原本不直接相连的两个车站 $a$ 和 $b$，用假铁路将它们直接连接。此操作重复 $K$ 次。
2. 在其中一个车站上做特殊标记。
3. 最后，抹去所有车站的编号。

叛徒将最终修改后的图纸发送给 A 国。仅凭这些信息，很难判断图纸是 B 国的铁路网络图，因此无人会察觉信息泄露。

为了使计划成功，需要解决以下问题：

• A 国收到的图纸中车站编号被抹去，且无法区分真假铁路。唯一可知的是哪个车站有特殊标记，以及假铁路的总数为 $K$ 条。
• 因此，发送方需要在图纸中以适当方式添加假铁路，并选择适当的车站做特殊标记，以便接收方仅凭图纸就能区分真假铁路。
• 接收方需要理解发送方的修改方法，并从收到的图纸中还原出原始铁路网络图。

如上所述，需要一个用于修改铁路网络图的函数和一个从图纸中还原原始铁路网络的函数。A 国将这项任务交给了你。

实现细节

你需要实现以下两个函数：

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

• 参数 $N$ 表示 B 国铁路网络中的车站数量 $N$。所有车站用 $1$ 到 $N$ 的整数表示。
• 参数 $K$ 表示需要添加的假铁路数量 $K$。
• 参数 $X$ 用于记录特殊标记的车站编号。函数结束时，$X$ 必须存储一个 $1$ 到 $N$ 之间的整数。
• 参数 $E$ 是一个大小为 $N-1$ 的数组，表示 B 国的铁路网络。每个二元组 $(a, b)$ 表示车站 $a$ 和 $b$ 直接通过铁路相连。
• 此函数返回一个包含 $K$ 个二元组 $(a, b)$ 的数组，表示添加的假铁路连接的车站。无论是真铁路还是假铁路，都不能重复连接同一对车站。

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

• 参数 $N$ 表示B国铁路网络中的车站数量 $N$。由于车站编号被抹去，此函数中使用的编号可能与原始编号不同（即通过某种双射函数重新编号）。
• 参数 $K$ 表示添加的假铁路数量 $K$。
• 参数 $X$ 表示带有特殊标记的车站编号。
• 参数 $E$ 是一个大小为 $N+K-1$ 的数组，表示 A 国收到的图纸。每个二元组 $(a, b)$ 表示车站 $a$ 和 $b$ 直接通过真或假铁路相连。注意，$E$ 中元素是无序的。
• 此函数从 encode_map 生成的图纸中还原原始铁路网络，返回一个大小为 $N-1$ 的数组，包含 B 国的真实铁路网络。

提交的源代码中不得执行任何输入输出函数。

每个测试用例包含一个或多个独立场景。对于一个包含 $T$ 个场景的测试用例，调用上述函数的程序将按以下方式执行两次：

第一次执行时：

• encode_map 函数被调用 $T$ 次。
• encode_map 函数的执行结果被评分系统保存。
• decode_map 函数不会被调用。

第二次执行时：

• decode_map 函数被多次调用。每次调用时随机选择一个场景，并将该场景中 encode_map 生成的图纸作为输入。
• encode_map 函数不会被调用。

本题的程序运行时间和内存使用量以两次执行的总和计算。

输入格式

示例评测程序按以下格式接收输入：

• 第 $1$ 行：$T$

随后是 $T$ 个场景，每个场景的格式如下：

• 第 $1$ 行：$N \ K$
• 第 $1+i$ 行（$1 \leq i \leq N-1$）：$a_i \ b_i$

$a_i, b_i$ 表示 $a_i$ 号车站和 $b_i$ 号车站之间存在铁路。

输出格式

示例评测程序针对每个场景输出以下格式：

• 第 $1$ 行：encode_map 返回的数组
• 第 $2$ 行：decode_map 返回的数组

注意：示例评测程序与实际评测程序可能不同。

2
6 1
1 2
1 3
1 4
4 5
4 6
5 2
2 3
4 3
4 5
1 3

提示

约束条件

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

子任务

1. （$4$ 分）
   • $N \leq 4$
2. （$13$ 分）
   • $K = 1$
3. （$11$ 分）
   • 每个车站连接的铁路不超过两条。
4. （$29$ 分）
   • 任意一个车站最多通过 $\lfloor \frac{N}{2} \rfloor$ 条铁路可以到达另一个任意车站。
5. （$43$ 分）
   • 无额外约束。

评分标准

只有当 encode_map 生成的图纸正确，且 decode_map 准确还原铁路网络时，该数据点才被视为正确。特别地，如果 decode_map 返回的数组中包含任何假铁路，则该数据点得分为 $0$。两个函数返回的数组中元素的顺序不重要。

注意：每个子任务的得分是该子任务所有数据点得分的最小值。

示例

• 考虑当 $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$ 的条件。