配点 : $1900$ 点

問題文

すぬけ君は頂点に $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$ 個のケースが与えられるので、それぞれについて答えを求めてください。

制約

• $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$ では頂点 $1$ を選び、$1$ と $2$ をつなぐ辺を取り除いて $1$ と $3$ をつなぐ辺を追加することで $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

6
0
7

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