/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
頂点に 1 から N の番号がついた N 頂点 N 辺の連結な単純無向グラフ G が与えられます。i 番目の辺は頂点 u_i と頂点 v_i を双方向に結んでいます。
以下の Q 個のクエリに答えてください。
- 頂点 x_i から頂点 y_i に向かう単純パス（同じ頂点を 2 度通らないパス）が一意に定まるか判定せよ。
制約
- 3 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i\leq N
- i \neq j ならば (u_i,v_i) \neq (u_j,v_j)
- G は N 頂点 N 辺の連結な単純無向グラフ
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i < y_i\leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N u_1 v_1 u_2 v_2 \vdots u_N v_N Q x_1 y_1 x_2 y_2 \vdots x_Q y_Q
出力
Q 行出力せよ。
i\ (1 \leq i \leq Q) 行目には、頂点 x_i から頂点 y_i に向かう単純パスが一意に定まる場合 Yes、そうでない場合 No を出力せよ。
入力例 1
5 1 2 2 3 1 3 1 4 2 5 3 1 2 1 4 1 5
出力例 1
No Yes No
頂点 1 から 2 に向かう単純パスは (1,2),(1,3,2) と一意に定まらないので、 1 個目のクエリの答えは No です。
頂点 1 から 4 に向かう単純パスは (1,4) と一意に定まるので、2 個目のクエリの答えは Yes です。
頂点 1 から 5 に向かう単純パスは (1,2,5),(1,3,2,5) と一意に定まらないので、3 個目のクエリの答えは No です。
入力例 2
10 3 5 5 7 4 8 2 9 1 2 7 9 1 6 4 10 2 5 2 10 10 1 8 6 9 8 10 6 8 3 10 3 9 1 10 5 8 1 10 7 8
出力例 2
Yes No Yes Yes No No Yes No Yes No
Score : 500 points
Problem Statement
You are given a connected simple undirected graph G with N vertices numbered 1 to N and N edges. The i-th edge connects Vertex u_i and Vertex v_i bidirectionally.
Answer the following Q queries.
- Determine whether there is a unique simple path from Vertex x_i to Vertex y_i (a simple path is a path without repetition of vertices).
Constraints
- 3 \leq N \leq 2 \times 10^5
- 1 \leq u_i < v_i\leq N
- (u_i,v_i) \neq (u_j,v_j) if i \neq j.
- G is a connected simple undirected graph with N vertices and N edges.
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i < y_i\leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N u_1 v_1 u_2 v_2 \vdots u_N v_N Q x_1 y_1 x_2 y_2 \vdots x_Q y_Q
Output
Print Q lines.
The i-th line (1 \leq i \leq Q) should contain Yes if there is a unique simple path from Vertex x_i to Vertex y_i, and No otherwise.
Sample Input 1
5 1 2 2 3 1 3 1 4 2 5 3 1 2 1 4 1 5
Sample Output 1
No Yes No
The simple paths from Vertex 1 to 2 are (1,2) and (1,3,2), which are not unique, so the answer to the first query is No.
The simple path from Vertex 1 to 4 is (1,4), which is unique, so the answer to the second query is Yes.
The simple paths from Vertex 1 to 5 are (1,2,5) and (1,3,2,5), which are not unique, so the answer to the third query is No.
Sample Input 2
10 3 5 5 7 4 8 2 9 1 2 7 9 1 6 4 10 2 5 2 10 10 1 8 6 9 8 10 6 8 3 10 3 9 1 10 5 8 1 10 7 8
Sample Output 2
Yes No Yes Yes No No Yes No Yes No