分数: 500 点
问题陈述
给你一个连通的简单无向图 G 与 N 顶点编号 1 to N 和 N 边缘。的 i第一条边连接顶点 u_i 和顶点 v_i 双向。
回答以下问题 Q 查询。
- 判断是否存在从Vertex出发的唯一简单路径 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 如果存在来自 Vertex 的唯一简单路径 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
来自 Vertex 的简单路径 1 to 2 是 (1,2) 和 (1,3,2),它们不是唯一的,因此第一个查询的答案是 No.
来自 Vertex 的简单路径 1 to 4 is (1,4),这是唯一的,所以第二个查询的答案是 Yes.
来自 Vertex 的简单路径 1 to 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