F - Natsuo良定义的路径查询

得分：500分

问题描述

给定一个有$N$个顶点从1到N编号，有N条边的连通简单无向图$G$。第$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)$，如果$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。

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