The IOI nation is uniquely built on an island in the shape of a regular $N$-gon. There is a region at each of the $N$ vertices, and these regions are numbered $0, 1, \dots, N-1$ in clockwise order. The road network of the IOI nation consists of two types of roads:

• Beach roads: Beach roads are the $N$ roads connecting regions corresponding to adjacent vertices of the regular $N$-gon. In other words, for every integer $0 \le i \le 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$.
• Land roads: There are a total of $N-3$ land roads that connect two regions not directly connected by a beach road in the form of a line segment. At this time, each land road does not meet others except at their endpoints. That is, they correspond to $N-3$ non-intersecting diagonals in the regular $N$-gon.

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

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

Since a tree connects all regions, it plays a very important role in transportation. However, it would be a great help to stability if there were another tree that could be used when the roads of a tree cannot be used. Therefore, we define a road network as a "good road network" if there exist two trees $T_1$ and $T_2$ in the road network such that $T_1 \cap T_2 = \emptyset$, that is, there exist two trees that do not share any roads.

The IOI nation intends to build a good road network through the following method of constructing new regions and roads:

• Region construction: For regions $a, b, c$, if roads directly connecting $a$ and $b$, $b$ and $c$, and $c$ and $a$ all exist, create a new region $d$ at the incenter of the triangle formed by the three regions, and connect $a$ and $d$, $b$ and $d$, and $c$ and $d$ with roads. The number of the new region $d$ is assigned sequentially starting from $N$. The same set of three regions cannot be used for region construction more than once. In other words, the set $\{a, b, c\}$ used in region construction must be different for each construction.

The IOI nation can perform region construction multiple times, but it wants to change it into a good road network where two non-overlapping trees exist through as few region constructions as possible. Note that to be a good road network, there must exist two non-overlapping trees that connect not only the existing $N$ regions but also the newly constructed regions. You must help the IOI nation solve the road network problem. Note that you can receive partial points even if you do not minimize the number of region constructions.

Implementation Details

You must 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 every integer $0 \le i \le N-4$, there exists a land road connecting region $U[i]$ and region $V[i]$.
• This function is called only once, and within this function, you must call the add_vertex function (defined below) to construct regions, find two trees that do not share roads, and call the report function.

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

• This function represents region construction for regions $a, b, c$.
• Before executing the function, any two of the regions $a, b, c$ must be directly connected by a road.
• This function must not be called more than once for the same three regions. In other words, the set $\{a, b, c\}$ used in region construction must be different for each call.
• This function returns the number of the newly constructed region. That is, when this function is executed for the $j$-th time, it returns $N-1+j$.
• This function must not be called after the report function has been called at least once.

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

• This function is for finding and reporting a tree in the road network.
• This function must be called exactly twice after all calls to the add_vertex function in construct_two_trees have finished.
• Each element of the parameter tree must be an std::array<int, 2> containing the numbers of the two regions connected by the road. At this time, the order of the two region numbers does not matter.
• When the two calls are report(T1) and report(T2), $T_1$ and $T_2$ must not share any roads, and for $1 \le k \le 2$, it must be possible to travel between all regions, including those created by add_vertex, using only the edges of $T_k$.

You must not execute input/output functions in any part of the submitted source code.

Constraints

• $3 \le N \le 200\,000$
• For all $0 \le i \le N-4$:
  • $0 \le U[i], V[i] \le N-1$
  • $U[i] \neq V[i]$
• The given $U$ and $V$ satisfy the land road conditions in the problem statement.

Subtasks

1. (6 points)
   • $N \le 5$
2. (8 points)
   • There exists a region directly connected by a road to all other regions except itself.
3. (14 points)
   • For all pairs of regions $(a, b, c)$ where region construction is possible in the initial state, at least one of the three roads connecting them is a beach road.
4. (21 points)
   • $N \le 5\,000$
5. (51 points)
   • No additional constraints.

When the construct_two_trees function solves the problem correctly, if the number of calls to add_vertex is greater than the minimum but does not exceed $N$, you receive 40% of the points for each subtask. If you call add_vertex more than $N$ times, you do not receive any points. It can be proven that under the constraints, a good road network can be constructed by calling add_vertex at most $N$ times.

Examples

Example 1

Consider the case where $N = 4, U = [0], V = [2]$. The grader calls the function as follows:

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

After that, when add_vertex(0, 2, 3) is called, the road network is in the following state:

After that, if report([[0,1],[0,2],[0,3],[4,2]]) and report([[4,0],[3,4],[2,3],[2,1]]) are called in order, this is an execution that correctly reports two trees. The two called trees are represented in red and blue, respectively, as shown in the figure below.

Note

The sample grader receives input in the following format:

Input 1

N
U[0] V[0]
U[1] V[1]
...
U[N-4] V[N-4]

Output 1

k
M
A[1] B[1]
A[2] B[2]
...
A[M] B[M]

Note

First, every time the report function is called, the grader outputs the $k$-th call, the number of roads $M$, and the endpoints of each road. After all executions of construct_two_trees have finished, the grader outputs the total number of calls $K$ to add_vertex, followed by the parameters $A[i], B[i], C[i]$ for each call. Note that the sample grader may differ from the grader used in actual grading.