Codeforces Round 345 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dfs and similar

dsu

greedy

trees

*3200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Clockwork Bomb

time limit per test

6 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMy name is James diGriz, I'm the most clever robber and treasure hunter in the whole galaxy. There are books written about my adventures and songs about my operations, though you were able to catch me up in a pretty awkward moment.

I was able to hide from cameras, outsmart all the guards and pass numerous traps, but when I finally reached the treasure box and opened it, I have accidentally started the clockwork bomb! Luckily, I have met such kind of bombs before and I know that the clockwork mechanism can be stopped by connecting contacts with wires on the control panel of the bomb in a certain manner.

I see *n* contacts connected by *n* - 1 wires. Contacts are numbered with integers from 1 to *n*. Bomb has a security mechanism that ensures the following condition: if there exist *k* ≥ 2 contacts *c*_{1}, *c*_{2}, ..., *c*_{k} forming a circuit, i. e. there exist *k* distinct wires between contacts *c*_{1} and *c*_{2}, *c*_{2} and *c*_{3}, ..., *c*_{k} and *c*_{1}, then the bomb immediately explodes and my story ends here. In particular, if two contacts are connected by more than one wire they form a circuit of length 2. It is also prohibited to connect a contact with itself.

On the other hand, if I disconnect more than one wire (i. e. at some moment there will be no more than *n* - 2 wires in the scheme) then the other security check fails and the bomb also explodes. So, the only thing I can do is to unplug some wire and plug it into a new place ensuring the fact that no circuits appear.

I know how I should put the wires in order to stop the clockwork. But my time is running out! Help me get out of this alive: find the sequence of operations each of which consists of unplugging some wire and putting it into another place so that the bomb is defused.

Input

The first line of the input contains *n* (2 ≤ *n* ≤ 500 000), the number of contacts.

Each of the following *n* - 1 lines contains two of integers *x*_{i} and *y*_{i} (1 ≤ *x*_{i}, *y*_{i} ≤ *n*, *x*_{i} ≠ *y*_{i}) denoting the contacts currently connected by the *i*-th wire.

The remaining *n* - 1 lines contain the description of the sought scheme in the same format.

It is guaranteed that the starting and the ending schemes are correct (i. e. do not contain cicuits nor wires connecting contact with itself).

Output

The first line should contain *k* (*k* ≥ 0) — the minimum number of moves of unplugging and plugging back some wire required to defuse the bomb.

In each of the following *k* lines output four integers *a*_{i}, *b*_{i}, *c*_{i}, *d*_{i} meaning that on the *i*-th step it is neccesary to unplug the wire connecting the contacts *a*_{i} and *b*_{i} and plug it to the contacts *c*_{i} and *d*_{i}. Of course the wire connecting contacts *a*_{i} and *b*_{i} should be present in the scheme.

If there is no correct sequence transforming the existing scheme into the sought one, output -1.

Examples

Input

3

1 2

2 3

1 3

3 2

Output

1

1 2 1 3

Input

4

1 2

2 3

3 4

2 4

4 1

1 3

Output

3

1 2 1 3

4 3 4 1

2 3 2 4

Note

Picture with the clarification for the sample tests:

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 04:30:32 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|