问题描述

Snuke发现了两棵树$A$和$B$，每棵树都有$N$个顶点，编号从$1$到$N$。$A$的第$i$条边连接了顶点$a_i$和$b_i$，$B$的第$j$条边连接了顶点$c_j$和$d_j$。此外，$A$的所有顶点最初都被涂成白色。

Snuke希望在$A$上执行以下操作零次或多次，使得$A$与$B$重合：

• 选择一个被涂成白色的叶子顶点（设为$v$）。
• 删除与$v$ 相接触的边，并添加一条连接$v$与另一个顶点的新边。
• 把$v$涂成黑色。

判断$A$是否能够与$B$重合，不考虑颜色。如果可以，请找出所需的最小操作次数。

输入包括$T$个这样的问题实例。对每个实例求解。

约束条件

• $1 \\leq T \\leq 20$
• $3 \\leq N \\leq 50$
• $1 \\leq a_i,b_i,c_i,d_i \\leq N$
• 所给图均为树。

输入

从标准输入读取输入数据，输入格式如下：

$T$ $case_1$ $:$ $case_{T}$

每个问题实例的输入格式如下：

$N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ $:$ $c_{N-1}$ $d_{N-1}$

输出

对于每个问题实例，如果$A$可以与$B$重合（不考虑颜色），则输出所需的最小操作次数；如果不能，则输出-1。

示例输入1

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

示例输出1

1
-1

• 每个问题实例的图示如下。
• 在第一个问题实例中，可以通过选择顶点$1$，删除连接$1$和$2$的边，并添加连接$1$和$3$的边，使得$A$与$B$重合。请注意，顶点$2$不是叶子顶点，因此无法选择。
• 在第二个问题实例中，$A$无法与$B$重合。

示例输入2

3
8
2 7
4 8
8 6
7 1
7 3
5 7
7 8
4 2
5 2
1 2
8 1
3 2
2 6
2 7
4
1 2
2 3
3 4
3 4
2 1
3 2
9
5 3
4 3
9 3
6 8
2 3
1 3
3 8
1 7
4 1
2 8
9 6
3 6
3 5
1 8
9 7
1 6

示例输出2

6
0
7

• $A$可以从一开始就与$B$重合。