Problem Statement

There is a tree with $N$ vertices numbered $1$ through $N$. The $i$-th of the $N-1$ edges connects vertices $a_i$ and $b_i$.

Initially, each edge is painted blue. Takahashi will convert this blue tree into a red tree, by performing the following operation $N-1$ times:

• Select a simple path that consists of only blue edges, and remove one of those edges.
• Then, span a new red edge between the two endpoints of the selected path.

His objective is to obtain a tree that has a red edge connecting vertices $c_i$ and $d_i$, for each $i$.

Determine whether this is achievable.

Constraints

• $2 ≤ N ≤ 10^5$
• $1 ≤ a_i,b_i,c_i,d_i ≤ N$
• $a_i ≠ b_i$
• $c_i ≠ d_i$
• Both input graphs are trees.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}

Output

Print YES if the objective is achievable; print NO otherwise.