题目描述

点击这里查看pdf

MianKing has two labeled unrooted trees $S$,$T$ with $n$ nodes and he wants to transform $S$ to $T$ by some operations.

In each operation, MianKing can select four distinct nodes $x,y,z,w$ which forms a path $\\\\{(x,y),(y,z),(z,w)\\\\}$ in the tree $S$. Then he removes edges $\\\\{(x,y),(y,z),(z,w)\\\\}$ from $S$ , chooses three new edges whose endpoints $\\in \\\\{x,y,z,w\\\\}$ and adds these new edges to $S$. MianKing has to guarantee that $S$ is still a tree after this operation.

Now you need to help MianKing to transform $S$ to $T$ within $10^4$ operations.

输入格式

The first line has one integer $n$.

Then there are $n-1$ lines, each lines has two integers $(x,y)$ which denotes an edge in $S$.

Then there are $n-1$ lines, each lines has two integers $(x,y)$ which denotes an edge in $T$.

$4\\leq n\\leq 100$

It's guaranteed that $S$ and $T$ are both trees.

输出格式

The first line has one string "YES" if there exists a solution to transform $S$ to $T$ within $10^4$ operations, otherwise "NO". (both without quotation)

If there exists a solution, then:

The first line has one integers $m$ which denotes the number of operations of your solution.

Then for each operations, there are two lines which represent this operations. The first line has four integers $(x,y,z,w)$ and the second line has six integers $a_1,b_1,a_2,b_2,a_3,b_3$ which $(a_i,b_i)$ denotes the i-th new edge you choose in this operation.

For each operation, you should guarantee these conditions:

1. $1\\leq x,y,z,w,a_i,b_i\\leq n$

2. $x,y,z,w$ are distinct and form a path $\\\\{(x,y),(y,z),(z,w)\\\\}$ in the tree $S$ at that time.

3. $a_i,b_i \\in \\\\{x,y,z,w\\\\}$

4. After removing edges $\\\\{(x,y),(y,z),(z,w)\\\\}$ and add new edges $(a_1,b_1),(a_2,b_2),(a_3,b_3)$, $S$ is still a tree at that time.

5. After all of the operations, $S$ should be the same as $T$.

6. $0\\leq m\\leq 10^4$

Two labeled tree are same if and only if $[(x,y)\\in S] \\leftrightarrow [(x,y)\\in T]$ for all edge $(x,y)$

样例

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

YES 
2 
5 2 3 4 
2 3 3 5 3 4 
1 2 3 5 
1 5 1 2 2 3

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

NO 

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

YES 
0 

提示

Form 2020ICPC济南站