题目描述

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

题目大意

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

3
1 2
2 3
1 3
3 2

YES

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

YES

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

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