{"raw_statement":[{"iden":"problem statement","content":"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$.\nInitially, each edge is painted blue. Takahashi will convert this blue tree into a red tree, by performing the following operation $N-1$ times:\n\n*   Select a simple path that consists of only blue edges, and remove one of those edges.\n*   Then, span a new red edge between the two endpoints of the selected path.\n\nHis objective is to obtain a tree that has a red edge connecting vertices $c_i$ and $d_i$, for each $i$.\nDetermine whether this is achievable."},{"iden":"constraints","content":"*   $2 ≤ N ≤ 10^5$\n*   $1 ≤ a_i,b_i,c_i,d_i ≤ N$\n*   $a_i ≠ b_i$\n*   $c_i ≠ d_i$\n*   Both input graphs are trees."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n:\n$a_{N-1}$ $b_{N-1}$\n$c_1$ $d_1$\n:\n$c_{N-1}$ $d_{N-1}$"},{"iden":"sample input 1","content":"3\n1 2\n2 3\n1 3\n3 2"},{"iden":"sample output 1","content":"YES\n\nThe objective is achievable, as below:\n\n*   First, select the path connecting vertices $1$ and $3$, and remove a blue edge $1-2$. Then, span a new red edge $1-3$.\n*   Next, select the path connecting vertices $2$ and $3$, and remove a blue edge $2-3$. Then, span a new red edge $2-3$."},{"iden":"sample input 2","content":"5\n1 2\n2 3\n3 4\n4 5\n3 4\n2 4\n1 4\n1 5"},{"iden":"sample output 2","content":"YES"},{"iden":"sample input 3","content":"6\n1 2\n3 5\n4 6\n1 6\n5 1\n5 3\n1 4\n2 6\n4 3\n5 6"},{"iden":"sample output 3","content":"NO"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}