102665: [AtCoder]ABC266 F - Well-defined Path Queries on a Namori

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

问题描述

给你一个连接的简单无向图$G$，包含$N$个编号为$1$到$N$的顶点和$N$条边。第$i$条边连接顶点$u_i$和顶点$v_i$双向。

回答以下$Q$个查询。

• 判断是否存在从顶点$x_i$到顶点$y_i$的唯一简单路径（简单路径是不重复顶点的路径）。

约束条件

• $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$是一个包含$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)$ 应包含 Yes，如果存在从顶点$x_i$到顶点$y_i$的唯一简单路径，否则包含 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)$，它们不是唯一的，因此第一个查询的答案是 No。

从顶点$1$到$4$的简单路径是$(1,4)$，它是唯一的，因此第二个查询的答案是 Yes。

从顶点$1$到$5$的简单路径有$(1,2,5)$和$(1,3,2,5)$，它们不是唯一的，因此第三个查询的答案是 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