AT_agc014_e [AGC014E] Blue and Red Tree

[problemUrl]: https://atcoder.jp/contests/agc014/tasks/agc014_e $ N $ 頂点からなる木があり、頂点には $ 1 $ から $ N $ の番号がついています。 また、 $ N-1 $ 本の辺の内、$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 はじめ、各辺は青色に塗られています。 そこで、高橋君は以下の操作を $ N-1 $ 回行い、赤色の木に作り替えることにしました。 - 青色の辺のみからなるパスを一つ選び、そのパス上の辺を一つ取り除く。 - その後、初めに選んだパスの両端点間に赤色の辺を追加する。 最終的に、各 $ i $ に対し、頂点 $ c_i $ と頂点 $ d_i $ を結ぶ赤い辺が存在するような $ N $ 頂点の木に作り替えたいです。 これが可能であるかどうか判定してください。

N/A

N/A

### 制約 - $ 2\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ a_i,b_i,c_i,d_i\ ≦\ N $ - $ a_i\ ≠\ b_i $ - $ c_i\ ≠\ d_i $ - 入力で与えられるグラフはどちらも木である。 ### Sample Explanation 1 高橋君は以下の手順で目標の赤い木を作ることができます。 - まず、頂点 $ 1 $ と頂点 $ 3 $ を結ぶパスを選び、青い辺 $ 1-2 $ を削除する。そして、赤い辺 $ 1-3 $ を追加する。 - 次に、頂点 $ 2 $ と頂点 $ 3 $ を結ぶパスを選び、青い辺 $ 2-3 $ を削除する。そして、赤い辺 $ 2-3 $ を追加する。