这是一道交互题。
一场叛乱后，上层政府任命你担任这座城市的市长，负责重建。你需要在城市里修建 $ N $ 条通道。
这是一座有着 $ 2N $ 个依次编号为 $ 1,2,\dots,2N $ 街区的大城市，它们由 $ 2N-1 $ 条双向道路连通。换言之，城市的街区和道路构成一棵树。
所有通道都是单向的，你需要选定恰好 $ N $ 个街区作为入口，其余 $ N $ 个街区作为出口。$ N $ 条通道需要不重不漏地覆盖所有入口和出口。同时为了避免上层政府质疑通道的修建方案，不能存在两条通道 $ (a,b),(c,d) $，其中 $ a,c $ 为入口，$ b,d $ 为出口，满足 $ \operatorname{dis}(a,b)<\operatorname{dis}(a,d)<\operatorname{dis}(c,d) $。此处 $ \operatorname{dis}(x,y) $ 定义为街区 $ x $ 到街区 $ y $ 的距离，即最少经过的道路数。
然而叛军烧毁了很多资料，导致你只拥有一份年代久远的城市地图。现在的城市相较于你手上的地图描绘的城市早已经过了许多次扩建。你的地图只有现在的城市的街区 $ 1\dots N $ 和当时连通它们的 $ N-1 $ 条道路。但扩建不会破坏城市的布局：对扩建前的两条恰有一个公共街区的道路 $ (a,b),(b,c) $，扩建后 $ a $ 到 $ b $ 的最短路径和 $ b $ 到 $ c $ 的最短路径依旧只有一个公共街区 $ b $。
由于你暂时人手不足，你只有以下两种渠道收集信息：
- 给定一系列街区 $ A $ 和一系列街区 $ B $（需要满足 $ |B|>1 $），对 $ A $ 中每个街区 $ x $，你可以知道离 $ x $ 最远的在所有路径 $ (x,y)(y\in B) $ 上的街区（即以 $ x $ 为根时 $ B $ 中街区的 $ \operatorname{LCA} $）是否为一个给定点 $ P $。
- 给出两个街区 $ x,y $，你可以知道 $ \operatorname{dis}(x,y) $。
请完成修建通道的任务。
实现细节
你不需要，也不应当实现主函数。
你应当引入头文件 passageconstruction.h。
你应当实现如下函数：
std::vector<std::pair<int,int>> ConstructPassages(int N, const std::vector<std::pair<int,int>> &E);$ N $ 的含义如题目所述，$ E $ 为你的地图上的道路，你需要返回恰好 $ N $ 个pair，代表一组合法的修建方案。一个 pair 代表一条通道，其成员 first 为入口，second 为出口。特别地，如果无解，请返回一个空vector。
可调用函数：
std::vector<int> QueryLCA(const std::vector<int> &A, const std::vector<int> &B, int P);该函数代表一次操作 $ 1 $，$ A,B,P $ 的含义如上文所述。保证返回vector 的大小与A.size()相同，值只包含 $ 0 $ 和 $ 1 $，第 $ k $ 项（从 $ 0 $ 开始）为 $ 1 $ 当且仅当以 $ A_k $ 为根时 $ B $ 中街区的 $ \operatorname{LCA} $ 为 $ P $。
int GetDistance(int x,int y);查询距离，$ x,y $ 含义如上文所述。
int getSubtaskID();获取子任务编号。在样例交互库中该函数恒返回 $ 0 $。
保证城市在交互开始时已经确定，即交互库不自适应。
样例交互库
下发了 sample_grader.cpp 和 passageconstruction.h，你可以使用命令 g++ sample_grader.cpp <your source file> -o passageconstruction -O2 -std=c++14 生成可执行文件。
注意评测时交互库与样例交互库有所不同。
输入格式
第一行一个数 $ N $，含义如题目所述。
接下来 $ 2N-1 $ 行，每行两个数，代表城市的一条道路。注意 $ 1,2,\dots,N $ 需要满足前文所述的条件。
注意样例交互库不会检查输入文件是否合法，输入不合法时其行为未定义。
输出格式
交互库会在运行过程正常结束且答案正确时返回 $ 0 $，答案错误或交互错误时返回 $ 1 $。
当答案错误或交互错误时的提示信息如下：
Index out of range：街区编号不为 $ [1,2N] $ 内的整数。
Invalid construction plan：返回方案格式有误。
Condition not satisfied：返回方案不满足上文的条件。
Invalid type 1 query：执行操作 $ 1 $ 时未满足 $ |B|>1 $ 的条件。
当答案正确时的提示信息如下：
Accepted with a+b operations, sum of size(s)=c+d。其中 $ a,b $ 分别为操作 $ 1 $ 和操作 $ 2 $ 的次数，$ c=\sum |A|,d=\sum |B| $。
当无解时的提示信息如下：
Reported no solution with a+b operations, sum of size(s)=c+d。$ a,b,c,d $ 含义同上。
数据范围
记 $ C_1 $ 为操作 $ 1 $ 次数，$ C_2 $ 为操作 $ 2 $ 次数，$ S_1=\sum |A|,S_2=\sum |B| $。
| 子任务编号 | 分值 | $ N\le $ | $ C_1 $ 上限 | $ C_2 $ 上限 | $ S_1 $ 上限 | $ S_2 $ 上限 | 特殊性质 |
|---|---|---|---|---|---|---|---|
| 1 | $ 3 $ | $ 5 $ | $ 100 $ | $ 100 $ | $ 1\times10^4 $ | $ 1\times10^4 $ | |
| 2 | $ 6 $ | $ 100 $ | $ 2\times 10^4 $ | $ 1\times10^4 $ | $ 2\times 10^5 $ | $ 2\times 10^5 $ | |
| 3 | $ 8 $ | $ 1000 $ | $ 1\times10^5 $ | $ 4000 $ | $ 2\times 10^5 $ | $ 2\times 10^5 $ | A |
| 4 | $ 9 $ | $ 1000 $ | $ 1\times10^5 $ | $ 4000 $ | $ 2\times 10^5 $ | $ 2\times 10^5 $ | BC |
| 5 | $ 11 $ | $ 1000 $ | $ 5\times10^4 $ | $ 4000 $ | $ 2\times 10^5 $ | $ 1\times 10^5 $ | B |
| 6 | $ 12 $ | $ 1000 $ | $ 2.5\times 10^4 $ | $ 4000 $ | $ 2\times 10^5 $ | $ 1\times 10^5 $ | C |
| 7 | $ 14 $ | $ 1000 $ | $ 2.5\times 10^4 $ | $ 4000 $ | $ 2\times 10^5 $ | $ 1\times 10^5 $ | |
| 8 | $ 10 $ | $ 5000 $ | $ 5\times 10^4 $ | $ 1\times 10^5 $ | $ 5\times 10^5 $ | $ 2\times 10^5 $ | |
| 9 | $ 27 $ | $ 5000 $ | $ 1.5\times 10^4 $ | $ 1\times 10^4 $ | $ 2\times 10^5 $ | $ 5\times 10^4 $ |
特殊性质 A：城市的每个街区至多与两条道路直接连接。
特殊性质 B：城市的每个街区至多与三条道路直接连接。
特殊性质 C：保证你拥有的地图上的所有道路仍然存在。
评分方式：在一个子任务内，如果 $ C_1,C_2,S_1,S_2 $ 均 $ \le $ 对应上限，该子任务得满分。
否则设对应上限分别为 $ C_1^{Lim},C_2^{Lim},S_1^{Lim},S_2^{Lim} $，令 $ v=\max(\frac{C_1}{C_1^{Lim}},\frac{C_2}{C_2^{Lim}},\frac{S_1}{S_1^{Lim}},\frac{S_2}{S_2^{Lim}}) $。如果 $ v>2 $ 则该子任务得 $ 0 $ 分，否则该子任务得分为该子任务满分分值$ \times (1.4-0.5v)^2 $。
保证交互库运行时间在给定数据范围内 $ \le 0.1\text{s} $，空间 $ \le 64\text{MiB} $。子任务 $ 1\sim 7 $ 的时间限制为 $ 1\text{s} $，其余子任务的时间限制为 $ 2.4\text{s} $。