题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include<vector>
#include<array>
void construct_two_trees(int N, std::vector<int> U, std::vector<int> V);
int add_vertex(int a, int b, int c);
void report(std::vector<std::array<int, 2>> tree);

题目描述

题目译自 2024년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1 「섬」

IOI 国建立在一个正 $N$ 边形的岛屿上。每个顶点代表一个区域，这些区域按顺时针方向依次编号为 $0, 1, \cdots, N-1$。IOI 国的道路网络由以下两种道路组成：

• 海滨道路：海滨道路连接正 $N$ 边形相邻顶点对应的区域，共有 $N$ 条道路。也就是说，对于所有 $i$ $(0 \leq i \leq 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$ 的整数数组。对于所有 $i$ $(0 \leq i \leq 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 函数调用结束后，必须准确调用两次该函数。
• 参数 tree 的每个元素是一个包含两区域编号的数组 std::array<int, 2>。区域编号的顺序无关紧要。
• 两次调用 report(T1), report(T2) 时，$T_1$ 和 $T_2$ 不应共享道路，并且每棵树的道路应能连接所有区域，包括新建区域。

输入格式

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2+i$ $(0 \leq i \leq N-4)$ 行：$U[i]\,V[i]$

输出格式

示例评测程序按以下格式输出：

每次调用 report 函数时，评测程序输出：

• 第 $1$ 行：整数 $k$，表示第 $k$ 次调用 report 函数。
• 第 $2$ 行：树的道路数量 $M$
• 第 $2+i$ $(1 \leq i \leq M)$ 行：树的第 $i$ 条道路的两个端点编号 $A[i]\,B[i]$

在 construct_two_trees 函数执行完毕后，评测程序输出 add_vertex 函数的调用信息：

• 第 $1$ 行：add_vertex 函数的总调用次数 $K$
• 第 $1+i$ $(1 \leq i \leq K)$ 行：add_vertex 函数第 $i$ 次调用的参数 $A[i]\,B[i]\,C[i]$

4
0 2

1
4
0 1
0 2
0 3
4 2
2
4
4 0
3 4
2 3
2 1
1
0 2 3

提示

对于所有输入数据，满足：

• $3 \leq N \leq 2\cdot 10^5$
• 对于所有 $i$ $(0 \leq i \leq N-4)$：
  • $0 \leq U[i], V[i] \leq N-1$
  • $U[i] \neq V[i]$
• 给定的 $U$ 和 $V$ 满足内陆道路的条件。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$6$	$N \leq 5$
$2$	$8$	存在一个区域与除自己外的所有区域直接相连
$3$	$14$	初始状态下，对于所有可能的区域对 $(a, b, c)$，连接这三个区域的三条道路中至少有一条是海滨道路
$4$	$21$	$N \leq 5000$
$5$	$51$	无附加限制

当 construct_two_trees 函数正确解决了问题时，如果 add_vertex 的调用次数大于最小值但不超过 $N$，则可以获得 $40\%$ 的分数。如果 add_vertex 的调用次数超过 $N$，则无法获得分数。可以证明，在给定限制条件下，可以通过不超过 $N$ 次调用 add_vertex 构建良好道路网络。