Problem B
Subway

The Stockholm subway is very inefficient. The city does not look like it did when the current subway lines were built, meaning certain parts are highly overutilized while some lines are barely used.

Therefore, the city council has decided to rebuild the subway. Currently, the system consists of $N$ stations, with $N-1$ pairs of stations connected by tracks such that it is possible to travel between any pair of stations by subway. The council has developed a new plan that still consists of the same $N$ stations, but with another set of $N-1$ tracks (still in such a way that all stations are connected).

To minimize disruptions in the busy subway, the reconstruction must be performed one track at a time. Every weekend, a single track must be closed and a new track built. This means that there will always be $N-1$ tracks. Furthermore, it must always be possible to travel between any pair of stations after the constructions during a weekend.

Your task is to find a way of constructing the new subway network, such that these conditions hold. Your plan must use as few weekends as possible.

Input

The first line contains the integer $1\le N$. The next $N-1$ lines contains the tracks in the current subway system. Each track is described by two space-separated integers $a$ $b$ between $0$ and $N-1$, the zero-indexed numbers of the stations the track connects. It will be possible to travel between any pair of stations using a sequence of the tracks.

The next $N-1$ lines contains the tracks that should be part of the new subway system, in the same format.

Output

First, output the number of weekends $K$ your construction plan needs. Then, output $K$ lines, one for each weekend in chronological order. A line should contain four integers $a_1,b_1,a_2,b_2$, meaning that the track connecting $a_1$ and $b_1$ should be closed, and a track connecting $a_2$ and $b_2$ should be built.

Grading

Your solution will be graded on a set of subtasks. A subtask will consist of multiple test cases. To get the points for a subtask, your solution must pass all test cases that are part of the subtask.

3
0 1
1 2
0 1
0 2

1
2 1 2 0

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

2
3 0 3 2
0 2 1 2