{"problem":{"name":"Blue and Red Tree","description":{"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$. Initially, each edge is painted blue. Takahashi will convert this blue tre","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc014_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc014_e","tags":[],"sample_group":[["3\n1 2\n2 3\n1 3\n3 2","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$."],["5\n1 2\n2 3\n3 4\n4 5\n3 4\n2 4\n1 4\n1 5","YES"],["6\n1 2\n3 5\n4 6\n1 6\n5 1\n5 3\n1 4\n2 6\n4 3\n5 6","NO"]],"created_at":"2026-03-03 11:01:14"}}