分数 : $1900$ 分

问题陈述

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。

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$ 中，$A$ 可以通过选择顶点 $1$，删除连接 $1$ 和 $2$ 的边，并添加连接 $1$ 和 $3$ 的边来与 $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

6
0
7

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