Josh is a townplanner, and is in charge of the roads in his local village. The village contains $N$ houses numbered from $1$ to $N$.

A road configuration is a set of $N$ roads with each road connecting two different houses bidirectionally, such that every house is reachable from every other house using the roads. There is at most one road between any two houses.

Currently, there is a road configuration $S$, with the $i$-th road connecting houses $a_i$ and $b_i$. However, he wants to redesign the village so that ends up with a road configuration $T$, with the $i$-th road connecting houses $c_i$ and $d_i$.

Due to a limited supply of gravel, he can only make operations in which he moves one road, by repeatedly deleting a road and adding another road. However, so that people can still travel around, all houses must be reachable from all other houses at all times. Specifically:

• He chooses a road from the current road configuration, and deletes it. After deletion, every house must still be reachable from every other house using the roads.
• Then, he adds a road between any two different houses that do not already have a road between them.

Can you help him achieve his goal? For full points, you must use as few operations as possible.

Note: it does not matter which road in $S$ corresponds to which road in $T$.

Constraints

$3\le N\le 100$

$1\le a_i,b_i,c_i,d_i\le N,a_i\ne b_i,c_i\ne d_i$

No two houses have multiple roads between them in $S$, or multiple roads betweem them in $T$.

Every house is reachable from every other house using only the roads in $S$, and only the roads in $T$.

Scoring

It can be proven that there always exists a sequence of operations transforming the road configuration from $S$ to $T$ with at most $10N$ operations.

To score any points, your solution must use at most $10N$ operations. If you output a valid solution with the fewest possible number of operations, you will receive $100\mathrm{\%}$ of the points. Otherwise, if you output a valid solution with at most $10N$ operations, you will receive $50\mathrm{\%}$ of the points.

Input Specification

The first line contains a single integer, $N$.

The $i$-th of the following $N$ lines contains two space-separated integers, $a_i$ and $b_i$.

The $i$-th of the following $N$ lines contains two space-separated integers, $c_i$ and $d_i$.

Output Specification

On the first line, output an integer $M(0\le M\le 10N)$, indicating the number of operations you will make.

On each of the next $M$ lines, output a line in the form w x y z, indicating that you will remove a road between houses $w$ and $x$, and add a road between houses $y$ and $z$.

Sample Input

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

Sample Output

2
3 4 4 2
1 4 3 1