M. Moving Sticks
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The renowned creators of pick-up sticks have just released the sliding-sticks puzzle. The puzzle consists of $$$N-1$$$ sticks connected to $$$N$$$ pins placed in the plane in convex position, forming a planar tree, that is, a connected and acyclic structure with no crossings.

The puzzle comes assembled in an initial configuration $$$T$$$, and the goal is to transform it into the final configuration $$$T'$$$ illustrated on the game box.

However, there is an important mechanical limitation: a stick cannot be moved freely. The only valid move is called a slide and works as follows:

  • Consider two sticks $$$ab$$$ and $$$bc$$$. It is allowed to detach the common endpoint at $$$b$$$ of stick $$$ab$$$ and move it along stick $$$bc$$$, until connecting it to $$$c$$$.
  • At the end of the move, no two sticks are allowed to cross.

Example: sliding edge $$$12$$$ along edge $$$32$$$.

We say that two sticks cross if their segments have a point in common that is not a shared endpoint; see the explanation of the second example below.

Since you have a dinner coming up and are short on time, you decided to add an extra restriction: your goal is to find a sequence of at most $$$2N$$$ slides that transforms $$$T$$$ into $$$T'$$$.

Input

The first line of the input contains an integer $$$N$$$ $$$(3 \leq N \leq 10^{5})$$$, indicating the number of pins.

Each of the next $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(-10^{9} \le x_i, y_i \le 10^{9})$$$, the coordinates of the pins in the plane. The pins are given in counterclockwise order along the convex hull.

Then $$$N-1$$$ lines follow, each containing integers $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le N, a \ne b)$$$, indicating the sticks of the initial configuration $$$T$$$.

Finally, the next $$$N-1$$$ lines contain integers $$$a'$$$ and $$$b'$$$ $$$(1 \le a', b' \le N, a' \ne b')$$$, indicating the sticks of the final configuration $$$T'$$$. It is guaranteed that the pins are in convex position, that is, no three pins are collinear and, in the order in which they are given, they form a convex polygon (so no point lies inside this polygon). Additionally, the configurations $$$T$$$ and $$$T'$$$ are planar trees, that is, they have no crossings.

Output

Print an integer $$$M$$$ ($$$0 \leq M \leq 2N$$$), representing the number of slides. It is not necessary to minimize the number of slides; it can be proven that there is always a solution with at most $$$2N$$$ slides.

In the next $$$M$$$ lines, print three integers $$$a$$$, $$$b$$$, and $$$c$$$, indicating a slide in which edge $$$ab$$$ is modified by detaching the endpoint at $$$b$$$ and sliding it along edge $$$bc$$$, resulting in edge $$$ac$$$.

Examples
Input
3
0 0
1 0
0 1
1 2
2 3
1 3
2 3
Output
2
3 2 1
2 1 3
Input
4
0 0
1 0
1 1
0 1
1 2
2 3
2 4
1 2
1 3
1 4
Output
2
4 2 1
3 2 1
Note

Explanation for example 2

The figure below shows the sequence of operations from the initial state to the final state in Example 2. Notice that there is more than one solution.

The figure below shows an invalid slide. In configuration $$$T$$$, sliding edge $$$32$$$ along edge $$$21$$$ is invalid, because it creates a crossing between sticks $$$31$$$ and $$$42$$$.