基环树上的良定义路径查询

题目描述

给定一个具有 $N$ 个顶点（编号 $1$ 到 $N$）和 $N$ 条边的连通简单无向图 $G$。第 $i$ 条边双向连接顶点 $u_i$ 和顶点 $v_i$。

回答以下 $Q$ 个查询。

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

输入格式

输入按以下格式从标准输入给出：

$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 \le i \le Q$）中，如果从顶点 $x_i$ 到顶点 $y_i$ 存在唯一的简单路径，则输出 Yes，否则输出 No。

样例

5
1 2
2 3
1 3
1 4
2 5
3
1 2
1 4
1 5

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。

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

Yes
No
Yes
Yes
No
No
Yes
No
Yes
No

数据范围

• $3 \le N \le 2 \times 10^5$
• $1 \le u_i \lt v_i \le N$
• 当 $i \neq j$ 时，$(u_i,v_i) \neq (u_j,v_j)$
• $G$ 是具有 $N$ 个顶点和 $N$ 条边的连通简单无向图
• $1 \le Q \le 2 \times 10^5$
• $1 \le x_i \lt y_i \le N$
• 输入中的所有值均为整数