配点 : $1400$ 点

問題文

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

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

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

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

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

制約

• $2 \leq N \leq 10^5$
• $1 \leq a_i,b_i,c_i,d_i \leq N$
• $a_i \neq b_i$
• $c_i \neq 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 を出力せよ。

3
1 2
2 3
1 3
3 2

YES

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

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

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