题目描述

すぬけ君は頂点に $1$ から $N$ の番号がついた $N$ 頂点の木 $A,B$ を見つけました。 $A$ の $i$ 番目の辺は頂点 $a_i$ と $b_i$ をつないでいます。 $B$ の $j$ 番目の辺は頂点 $c_j$ と $d_j$ をつないでいます。 全ての頂点ははじめ、白で塗られています。

すぬけ君は以下の操作を $A$ に $0$ 回以上行い、$B$ と一致するようにしたいです。

• 白で塗られた葉を $1$ つ選ぶ(これを $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 を出力せよ。

题目大意

给定两棵 $n$ 个节点的树 $A,B$, 你需要对 $A$ 执行若干次操作, 每次操作选择一个叶子节点, 删除连接这个叶子的边，并将这个叶子节点连向任意一个另外的点, 每个点只能被选择一次.

求使得 $A,B$ 相同的最小的操作次数. 有 $T$ 组测试数据.

$T\leqslant 20, N\leqslant 50$.

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

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$
• 与えられるグラフはいずれも木

Sample Explanation 1

- それぞれのケースでは、以下の図のようなグラフが与えられます - ケース $1$ では頂点 $1$ を選び、$1$ と $2$ をつなぐ辺を取り除いて $1$ と $3$ をつなぐ辺を追加することで $A$ と $B$ を一致させることが可能です。頂点 $2$ は葉ではないため、選ぶことができないことに注意してください 

Sample Explanation 2

- $A$ と $B$ が一致していることもあります