AT_agc027_f [AGC027F] Grafting

[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` を出力せよ。

### 制約 - $ 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 $ が一致していることもあります