Subway

Time limit2sMemory limit1024 MB

Summary

Given two spanning trees on the same N stations, output a shortest sequence of weekend swaps, each removing one tree edge and adding another, so every intermediate graph stays a spanning tree and the target tree is reached.

Level: Hard8 of 10
Topics: Graph, Tree, Greedy, Union-find
Solved: No attempts yet

Problem

The Stockholm subway operates inefficiently. The city looks different from when the current lines were built, so some sections are heavily overused while other lines are barely used.

The city council has decided to rebuild the subway. The current system consists of $N$ stations, with $N - 1$ pairs of stations connected by tracks so that it is possible to travel between any pair of stations by subway. The council has made a new plan that uses the same $N$ stations but another set of $N - 1$ tracks that still connects all stations.

To minimize disruption in the busy subway, reconstruction must proceed one track at a time. Every weekend, exactly one track is closed and one new track is built. Hence there are always $N - 1$ tracks. Moreover, after the work of each weekend, it must still be possible to travel between any pair of stations.

Find a way to construct the new subway network so that these conditions hold. The plan must use as few weekends as possible.

Input

The first line contains an integer $N$ . $N$ is at least $1$ . The next $N - 1$ lines describe the tracks in the current subway system. Each track is described by two space-separated integers $a$ $b$ , the numbers of the stations the track connects. Station numbers run from $0$ to $N - 1$ and are zero-indexed. It is possible to travel between any pair of stations using these tracks.

The next $N - 1$ lines describe the tracks that must belong to the new subway system, in the same format. If $N$ is $1$ , there are no track lines.

Output

First, output the number of weekends $K$ required by the construction plan. Then output $K$ lines, one for each weekend in chronological order. Each line must contain four integers $a_1$ $b_1$ $a_2$ $b_2$ , meaning that the track connecting $a_1$ and $b_1$ is closed and a track connecting $a_2$ and $b_2$ is built.

After each weekend there must be exactly $N - 1$ tracks and all stations must stay connected, and after the last weekend the network must equal the target network. Among all plans satisfying the conditions, output one with the smallest possible number of weekends.

Examples2

Example 1
Input
```
3
0 1
1 2
0 1
0 2
```
Expected output
```
1
2 1 0 2
```

Example 2

Input

Expected output

2
2 0 1 2
3 0 2 3