[AGC027F] Grafting

给定两棵 $n$ 个节点的树 $A,B$, 你需要对 $A$ 执行若干次操作, 每次操作选择一个叶子节点, 删除连接这个叶子的边，并将这个叶子节点连向任意一个另外的点, 每个点只能被选择一次. 求使得 $A,B$ 相同的最小的操作次数. 有 $T$ 组测试数据. $T\leqslant 20, N\leqslant 50$.

[problemUrl]: https://atcoder.jp/contests/agc027/tasks/agc027_f すぬけ君は頂点に $ 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` を出力せよ。

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 $ は葉ではないため、選ぶことができないことに注意してください !\[3f020b4a4e883680357cc55adb571fbc.png\](https://img.atcoder.jp/agc027/3f020b4a4e883680357cc55adb571fbc.png) ### Sample Explanation 2 \- $ A $ と $ B $ が一致していることもあります