题目描述

すぬけ君发现了两棵有 $N$ 个顶点的树 $A$ 和 $B$，每个顶点编号为 $1$ 到 $N$。树 $A$ 的第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，树 $B$ 的第 $j$ 条边连接顶点 $c_j$ 和 $d_j$。所有顶点初始时都被涂成白色。

すぬけ君可以对 $A$ 进行如下操作若干次（可以为 $0$ 次），希望将 $A$ 变为与 $B$ 完全相同。

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

请判断是否可以通过上述操作将 $A$ 变为 $B$，如果可以，求所需操作次数的最小值。判断两棵树是否一致时，不考虑顶点的颜色。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入按以下格式从标准输入读入。

$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

样例 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

说明/提示

限制

• $1 \leq T \leq 20$
• $3 \leq N \leq 50$
• $1 \leq a_i, b_i, c_i, d_i \leq N$
• 输入的图均为树

样例解释 1

• 每组数据给出的图如下图所示。对于第 $1$ 组，可以选择顶点 $1$，移除 $1$ 与 $2$ 的边，并添加 $1$ 与 $3$ 的边，即可将 $A$ 变为 $B$。注意，顶点 $2$ 不是叶子，不能被选择。
  

样例解释 2

• 有时 $A$ 和 $B$ 已经一致。

由 ChatGPT 4.1 翻译