这是一道交互题。

一场叛乱后，上层政府任命你担任这座城市的市长，负责重建。你需要在城市里修建 $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$。

由于你暂时人手不足，你只有以下两种渠道收集信息：

1. 给定一系列街区 $A$ 和一系列街区 $B$（需要满足 $\|B\|>1$），对 $A$ 中每个街区 $x$，你可以知道离 $x$ 最远的在所有路径 $(x,y)(y\in B)$ 上的街区（即以 $x$ 为根时 $B$ 中街区的 $\operatorname{LCA}$）是否为一个给定点 $P$。
2. 给出两个街区 $x,y$，你可以知道 $\operatorname{dis}(x,y)$。

请完成修建通道的任务。

实现细节

你不需要，也不应当实现主函数。

你应当引入头文件 passageconstruction.h。

你应当实现如下函数：

std<span class="sh_symbol">::</span><span class="sh_usertype">vector<std::pair<int,int>> ConstructPassages(int N, const std::vector<std::pair<int,int>></span><span class="sh_normal">¨NBSP;</span><span class="sh_symbol">&</span>E<span class="sh_symbol">);</span>

$N$ 的含义如题目所述，$E$ 为你的地图上的道路，你需要返回恰好 $N$ 个pair，代表一组合法的修建方案。一个 pair 代表一条通道，其成员 first 为入口，second 为出口。特别地，如果无解，请返回一个空vector。

可调用函数：

std<span class="sh_symbol">::</span><span class="sh_usertype">vector<int> QueryLCA(const std::vector<int> &A, const std::vector<int></span><span class="sh_normal"> </span><span class="sh_symbol">&</span>B<span class="sh_symbol">,</span> <span class="sh_type">int</span> P<span class="sh_symbol">);</span>

该函数代表一次操作 $1$，$A,B,P$ 的含义如上文所述。保证返回vector 的大小与A.size()相同，值只包含 $0$ 和 $1$，第 $k$ 项（从 $0$ 开始）为 $1$ 当且仅当以 $A_k$ 为根时 $B$ 中街区的 $\operatorname{LCA}$ 为 $P$。

<span class="sh_type">int</span> <span class="sh_function">GetDistance</span><span class="sh_symbol">(</span><span class="sh_type">int</span> x<span class="sh_symbol">,</span><span class="sh_type">int</span> y<span class="sh_symbol">);</span>

查询距离，$x,y$ 含义如上文所述。

<span class="sh_type">int</span> <span class="sh_function">getSubtaskID</span><span class="sh_symbol">();</span>

获取子任务编号。在样例交互库中该函数恒返回 $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$		$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$			A
4	$9$						BC
5	$11$		$5\times10^4$			$1\times 10^5$	B
6	$12$		$2.5\times 10^4$				C
7	$14$
8	$10$	$5000$	$5\times 10^4$	$1\times 10^5$	$5\times 10^5$	$2\times 10^5$
9	$27$		$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}$。