IOI 国建立在一个形状为正 $N$ 边形的岛屿上。岛屿的 $N$ 个顶点处各有一个区域，这些区域按顺时针方向依次编号为 $0, 1, \dots, N-1$。IOI 国的道路网由以下两种道路组成：
- 海滨道路：海滨道路是连接正 $N$ 边形相邻顶点的 $N$ 条道路。换句话说，对于所有整数 $0 \le i \le N-2$，存在连接区域 $i$ 和区域 $i+1$ 的道路，且存在连接区域 $N-1$ 和区域 $0$ 的道路。
- 陆地道路：存在总共 $N-3$ 条陆地道路，它们以线段形式连接非海滨道路直接相连的两个区域。这些陆地道路在端点之外互不相交。也就是说，它们对应于正 $N$ 边形中互不相交的 $N-3$ 条对角线。
对于连接 $K$ 个区域的某个道路网，如果道路集合 $T$ 满足以下条件，则称 $T$ 为一棵树：
- $|T| = K - 1$
- 仅使用 $T$ 中包含的道路即可在所有区域之间移动。
树由于连接了所有区域，在运输中起着非常重要的作用。然而，如果存在另一棵树可以在无法使用当前树的道路时使用，将对稳定性有很大帮助。因此，如果道路网中存在两棵树 $T_1$ 和 $T_2$ 满足 $T_1 \cap T_2 = \emptyset$，即存在两条互不重叠的树，则称该道路网为“好的道路网”。
IOI 国希望通过以下方式建设新的区域和道路，从而构建好的道路网：
- 区域建设：对于区域 $a, b, c$，如果连接 $a$ 与 $b$、 $b$ 与 $c$ 以及 $c$ 与 $a$ 的道路都存在，则在三个区域构成的三角形内心处创建一个新区域 $d$，并连接 $a$ 与 $d$、 $b$ 与 $d$ 以及 $c$ 与 $d$。新区域 $d$ 的编号从 $N$ 开始依次递增。对于同一组三个区域，不能进行两次以上的区域建设。换句话说，区域建设中使用的集合 $\{a, b, c\}$ 在每次建设时必须互不相同。
IOI 国可以进行多次区域建设，但希望通过尽可能少的区域建设次数，将其转变为存在两条互不重叠的树的“好的道路网”。请注意，为了成为好的道路网，必须存在两条互不重叠的树，它们不仅连接原有的 $N$ 个区域，还连接新建设的区域。你需要帮助 IOI 国解决道路网问题。请注意，即使不最小化区域建设的次数，也可以获得部分分数。
实现细节
你需要实现以下函数：
void construct_two_trees(int N, std::vector<int> U, std::vector<int> V)- $U, V$：大小为 $N-3$ 的整数数组。对于所有整数 $0 \le i \le N-4$，存在连接区域 $U[i]$ 和区域 $V[i]$ 的陆地道路。
- 此函数仅被调用一次。你必须在此函数内调用稍后定义的
add_vertex函数来建设区域，并找到两条不共享道路的树，然后调用report函数。
int add_vertex(int a, int b, int c)- 此函数表示对区域 $a, b, c$ 进行区域建设。
- 在函数执行前，区域 $a, b, c$ 中任意两个区域都必须通过道路直接相连。
- 对于同一组三个区域，不得调用此函数两次以上。换句话说，区域建设中使用的集合 $\{a, b, c\}$ 在每次调用时必须互不相同。
- 此函数返回新建设区域的编号。即，当此函数第 $j$ 次执行时，返回 $N-1+j$。
- 此函数在
report函数被调用后不得再被调用。
void report(std::vector<std::array<int, 2> > tree)- 此函数用于查找并报告道路网中的树。
- 此函数必须在
construct_two_trees函数中所有add_vertex函数调用结束后，被准确调用 2 次。 - 参数
tree的每个元素必须是包含道路连接的两个区域编号的std::array<int, 2>。此时，两个区域编号的顺序无关紧要。 - 当两次调用分别为
report(T1)和report(T2)时，$T_1$ 和 $T_2$ 不得共享道路，且对于 $1 \le k \le 2$，仅通过 $T_k$ 的边，必须能够往返于包括通过add_vertex生成的区域在内的所有区域。
提交的源代码的任何部分都不应执行输入输出函数。
数据范围
- $3 \le N \le 200\,000$
- 对于所有 $0 \le i \le N-4$：
- $0 \le U[i], V[i] \le N-1$
- $U[i] \neq V[i]$
- 给定的 $U$ 和 $V$ 满足题目描述中的陆地道路条件。
子任务
- (6分) $N \le 5$
- (8分) 存在一个与除自身以外的所有区域都直接相连的区域。
- (14分) 在初始状态下，对于所有可以进行区域建设的区域三元组 $(a, b, c)$，连接它们的 3 条道路中至少有 1 条是海滨道路。
- (21分) $N \le 5\,000$
- (51分) 无额外限制。
当 construct_two_trees 函数正确解决了问题，且 add_vertex 的调用次数大于最小值但不超过 $N$ 时，获得各子任务分数的 40%。如果调用 add_vertex 超过 $N$ 次，则无法获得分数。在上述限制条件下，可以证明通过调用 add_vertex 不超过 $N$ 次即可构建好的道路网。
样例
样例 1
考虑 $N = 4, U = [0], V = [2]$ 的情况。 评测程序调用如下函数：
construct_two_trees(4, [0], [2])之后，当调用 add_vertex(0, 2, 3) 时，道路网状态如下：
之后，依次调用 report([[0,1],[0,2],[0,3],[4,2]]) 和 report([[4,0],[3,4],[2,3],[2,1]])，即为正确报告两棵树的执行。将调用的两棵树分别用红色和蓝色表示，如下图所示：
说明
Sample grader 接收以下格式的输入：
- Line 1: $N$
- Line 2 + $i$ ($0 \le i \le N-4$): $U[i] \ V[i]$
Sample grader 输出以下格式：
首先，每次调用 report 函数时，评测程序输出如下：
- Line 1: 整数 $k$。表示函数
report的第 $k$ 次调用。 - Line 2: 树的道路数 $M$
- Line 2 + $i$ ($1 \le i \le M$): 树的第 $i$ 条道路的两个端点编号 $A[i] \ B[i]$
之后，在 construct_two_trees 函数执行结束后，评测程序输出关于 add_vertex 函数调用的信息如下：
- Line 1:
add_vertex函数的总调用次数 $K$ - Line 1 + $i$ ($1 \le i \le K$):
add_vertex函数第 $i$ 次调用的参数 $A[i] \ B[i] \ C[i]$
请注意，Sample grader 可能与实际评分时使用的评测程序不同。