Contest Duration: - (local time) (100 minutes) Back to Home
F - Well-defined Path Queries on a Namori /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

• 頂点 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)
• GN 頂点 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


入力例 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.

• 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