# KOITST 24 Island

https://www.acmicpc.net/problem/31570

In the country of IOI, islands are peculiarly built in the shape of polygons with $N$ sides. There are regions at locations corresponding to each of the $N$ vertices, and these regions are numbered in counterclockwise order from $0$ to $N - 1$. The road network in IOI country consists of two types of roads:

Coastal roads: Coastal roads are $N$ roads connecting adjacent vertices of the $N$-polygon. In other words, for all integers $0 ≤ i ≤ N - 2$, there exists a road connecting region $i$ and region $i + 1$, and there exists a road connecting region $N - 1$ and region $0$.

Inland roads: There are a total of $N - 3$ inland roads that connect two regions not directly connected by coastal roads. In this case, each inland road does not intersect with each other except at their endpoints. In other words, there are $N - 3$ distinct non-intersecting diagonals in the $N$-polygon.

Moreover, for any road network connecting $K$ regions, the set of roads $T$ is called a tree when it satisfies the following conditions:

* $|T| = K - 1$
* It is possible to travel between all regions using only the roads included in $T$.

Since trees connect all regions, they play a crucial role in transportation. However, having an alternative tree to use when the roads of the original tree are unavailable would greatly contribute to stability. Thus, a road network is defined as a good road network when two trees $T_1$ and $T_2$ exist in the network such that $T_1 \cap T_2 = ∅$, meaning there are two trees without any overlapping roads.

IOI country aims to establish a good road network through the construction of new regions and roads. The construction plan is as follows:

* When there are direct roads between regions $a$, $b$, and $c$, a new region $d$ is created at the incenter of the triangle formed by these three regions. Roads are then constructed between $a$ and $d$, $b$ and $d$, and $c$ and $d$. The numbering of the new region $d$ starts from $N$ sequentially. Area construction cannot be repeated for the same three regions. In other words, the set used in area construction, ${a, b, c}$, must be different for each construction.

IOI country can perform area construction multiple times but aims to transform the road network into a good road network with as few area constructions as possible. Note that to become a good road network, it is necessary to connect not only the existing $N$ regions but also the newly constructed regions without overlapping two trees.

# Implementation

You need to implement the following functions:

`void construct_two_trees(int N, std::vector<int> U, std::vector<int> V)`

* U, V: Integer arrays of size $N - 3$. For all integers $0 ≤ i ≤ N - 4$, there is an inland road connecting region $U[i]$ and region $V[i]$.
* This function is called only once, and you must call the add_vertex function within this function to construct regions and find two trees with non-overlapping roads using the report function.

`int add_vertex(int a, int b, int c)`

* This function represents area construction for regions $a$, $b$, and $c$.
* Before calling this function, regions $a$, $b$, and $c$ must be directly connected by roads.
* This function returns the number of the newly constructed region. In other words, when this function is executed for the $j$-th time, it returns $N - 1 + j$.
* This function should not be called after the report function has been called even once.

`void report(std::vector<std::array<int, 2> > tree)`

* This function reports the trees found in the road network.
* This function must be called exactly twice after all calls to the add_vertex function have ended within the construct_two_trees function.
* Each element of parameter tree contains the numbers of two regions connected by a road in the road network.
* When called twice with report(T1) and report(T2), $T_1$ and $T_2$ should not share any roads, and for $1 ≤ k ≤ 2$, all regions, including those generated by the add_vertex function, should be accessible via the edges of $T_k$.

# Constraints

* $3 \le N \le 200,000$
* For all $0 ≤ i ≤ N - 4$:
* $0 ≤ U[i], V[i] ≤ N - 1$
* $U[i] \ne V[i]$
* The given $U$ and $V$ satisfy the conditions for inland roads as stated in the problem statement.

# Subtasks


If the `construct_two_trees` function correctly solves the problem, obtaining $40\%$ of the score in each subtask is possible when the number of calls to add_vertex is greater than the minimum but does not exceed $N$. Failure to construct the road network with fewer than $N$ calls to add_vertex results in no score. It can be proven that it is possible to construct a good road network by calling add_vertex at most $N$ times under the given constraints.

# Examples

Consider the case where $N = 4$, $U = [0]$, and $V = [2]$.

The grader calls the function as follows:

`construct_two_trees(4, [0], [2])`

Then, after calling `add_vertex(0, 2, 3)`, the road network is in the following state:


Subsequently, calling `report([[0,1],[0,2],[0,3],[4,2]])` followed by `report([[4,0],[3,4],[2,3],[2,1]])` is a correct execution of reporting two trees. If we represent the two trees with red and blue colors respectively, the illustration would be as follows: