Time Limit: 6 sec / Memory Limit: 256 MB
配点 : 1400 点
問題文
N 頂点からなる木があり、頂点には 1 から N の番号がついています。 また、 N-1 本の辺の内、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。
はじめ、各辺は青色に塗られています。 そこで、高橋君は以下の操作を N-1 回行い、赤色の木に作り替えることにしました。
- 青色の辺のみからなるパスを一つ選び、そのパス上の辺を一つ取り除く。
- その後、初めに選んだパスの両端点間に赤色の辺を追加する。
最終的に、各 i に対し、頂点 c_i と頂点 d_i を結ぶ赤い辺が存在するような N 頂点の木に作り替えたいです。
これが可能であるかどうか判定してください。
制約
- 2 ≦ N ≦ 10^5
- 1 ≦ a_i,b_i,c_i,d_i ≦ N
- a_i ≠ b_i
- c_i ≠ 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
を出力せよ。
入力例 1
3 1 2 2 3 1 3 3 2
出力例 1
YES
高橋君は以下の手順で目標の赤い木を作ることができます。
- まず、頂点 1 と頂点 3 を結ぶパスを選び、青い辺 1-2 を削除する。そして、赤い辺 1-3 を追加する。
- 次に、頂点 2 と頂点 3 を結ぶパスを選び、青い辺 2-3 を削除する。そして、赤い辺 2-3 を追加する。
入力例 2
5 1 2 2 3 3 4 4 5 3 4 2 4 1 4 1 5
出力例 2
YES
入力例 3
6 1 2 3 5 4 6 1 6 5 1 5 3 1 4 2 6 4 3 5 6
出力例 3
NO
Score : 1400 points
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.
Sample Input 1
3 1 2 2 3 1 3 3 2
Sample Output 1
YES
The objective is achievable, as below:
- First, select the path connecting vertices 1 and 3, and remove a blue edge 1-2. Then, span a new red edge 1-3.
- Next, select the path connecting vertices 2 and 3, and remove a blue edge 2-3. Then, span a new red edge 2-3.
Sample Input 2
5 1 2 2 3 3 4 4 5 3 4 2 4 1 4 1 5
Sample Output 2
YES
Sample Input 3
6 1 2 3 5 4 6 1 6 5 1 5 3 1 4 2 6 4 3 5 6
Sample Output 3
NO