Score : 1400 points
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:
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.
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}
Print YES
if the objective is achievable; print NO
otherwise.
3 1 2 2 3 1 3 3 2
YES
The objective is achievable, as below:
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