問題文

$N$ 頂点からなる木があり、頂点には $1$ から $N$ の番号がついています。 また、 $N-1$ 本の辺の内、$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

はじめ、各辺は青色に塗られています。 そこで、高橋君は以下の操作を $N-1$ 回行い、赤色の木に作り替えることにしました。

• 青色の辺のみからなるパスを一つ選び、そのパス上の辺を一つ取り除く。
• その後、初めに選んだパスの両端点間に赤色の辺を追加する。

最終的に、各 $i$ に対し、頂点 $c_i$ と頂点 $d_i$ を結ぶ赤い辺が存在するような $N$ 頂点の木に作り替えたいです。

これが可能であるかどうか判定してください。

制約

• $2 ≦ N ≦ 10^5$
• $1 ≦ a_i,b_i,c_i,d_i ≦ N$
• $a_i ≠ b_i$
• $c_i ≠ d_i$
• 入力で与えられるグラフはどちらも木である。

入力

入力は以下の形式で標準入力から与えられる。

$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

高橋君は以下の手順で目標の赤い木を作ることができます。

• まず、頂点 $1$ と頂点 $3$ を結ぶパスを選び、青い辺 $1-2$ を削除する。そして、赤い辺 $1-3$ を追加する。
• 次に、頂点 $2$ と頂点 $3$ を結ぶパスを選び、青い辺 $2-3$ を削除する。そして、赤い辺 $2-3$ を追加する。

入力例 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