Island Construction

In IOI Kingdom, the original island is built on a regular $N$–gon. Each vertex represents a region, numbered $0,1,\ldots,N-1$ in clockwise order. There are two types of roads:

• Coastal roads: These connect adjacent vertices (i.e. regions) along the boundary of the $N$–gon. There are exactly $N$ such roads connecting region $i$ and region $(i+1)$ for $0 \le i \le N-2$, plus one connecting regions $N-1$ and $0$.
• Inland roads: These are the $N-3$ non‐crossing diagonals of the $N$–gon connecting non-adjacent regions.

A set of roads $T$ is called a tree connecting $K$ regions if:

[ |T| = K-1 \quad \text{and} \quad T \text{ connects all regions.} ]

A road network is called a good road network if there exist two trees, say $T_1$ and $T_2$, with no common road ($T_1 \cap T_2=\emptyset$) and such that even if one tree’s roads become unusable, the other still provides connectivity among all regions.

IOI Kingdom can add new regions via the following construction: if three regions $a$, $b$, $c$ are pairwise connected by roads (so that they form a triangle), a new region $d$ is built at the incenter of the triangle and connected to $a$, $b$, and $c$. The first new region is numbered $N$, and subsequent regions are numbered consecutively. Each triple ({a,b,c}) may be used at most once.

The task is to construct a good road network (i.e. to obtain two edge–disjoint spanning trees covering all regions, including any new ones) while performing as few region constructions as possible (though even a non–minimal solution earns partial credit).

You are to implement the function:

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

Here, the arrays U and V (each of length $N-3$) describe the inland roads: for every valid index i, there is a road between regions U[i] and V[i].

Before reporting your two trees, you may call the provided add_vertex function:

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

This creates a new region at the incenter of the triangle formed by regions a, b, and c (which must be pairwise connected by existing roads) and connects it to those regions. Each such call returns the new region’s id (the first call returns N, then N+1, etc.).

Finally, call the function report twice:

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

Each call reports one spanning tree (each tree must have exactly K-1 roads where K is the total number of regions, including any new ones). The two reported trees must be edge–disjoint.

Example Strategy (Not necessarily optimal):

A valid approach is to perform one region construction using regions 0, 1, and 2 (which are adjacent along the coastal road) to create a new region d (with id N). Then construct:

• Tree 1: Use the coastal roads except one edge to form a spanning tree on regions 0..N-1 and add the new road (0, d).
• Tree 2: Use all inland roads, add the missing coastal edge (the one not used in tree 1) and the remaining new roads (1, d) and (2, d) to form a spanning tree.

This yields two spanning trees on all regions (original and the new one) with no overlapping road.

Note: Your solution must work for all valid inputs.

inputFormat

The first line contains an integer $N$ ($N \ge 3$) representing the number of vertices of the original island. Each of the next $N-3$ lines contains two integers representing an inland road between regions (the arrays U and V in order).

outputFormat

Your program should output two spanning trees. For each tree, first output the number of edges (which should equal the total number of regions minus one), followed by that many lines each containing two integers (the endpoints of each road in the tree). The two trees must be edge–disjoint and together cover all regions (including any new ones built via add_vertex).

sample

3

2
0 1
1 2
2
2 0
(plus appropriate new road connecting region 0,1,2 with new region 3)\n

</p>