[AGC014E] Blue and Red Tree

题意翻译

给定一棵$n$个节点的树,一开始所有边都是蓝色的。每次选择一条所有边都是蓝色的路径,删掉其中一条边,然后在路径的两个端点之间连一条红边。求最后能不能得到目标形态(都是红边)的树。

题目描述

[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_1 $ $ b_1 $ : $ a_{N-1} $ $ b_{N-1} $ $ c_1 $ $ d_1 $ : $ c_{N-1} $ $ d_{N-1} $

输出格式


高橋君が木を目標の木に作り替えられるならば `YES` を、作り替えられないならば `NO` を出力せよ。

输入输出样例

输入样例 #1

3
1 2
2 3
1 3
3 2

输出样例 #1

YES

输入样例 #2

5
1 2
2 3
3 4
4 5
3 4
2 4
1 4
1 5

输出样例 #2

YES

输入样例 #3

6
1 2
3 5
4 6
1 6
5 1
5 3
1 4
2 6
4 3
5 6

输出样例 #3

NO

说明

### 制約 - $ 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 $ を追加する。