← 返回题目列表

AtCoder · abc266_f

I. Namori 上明确定义的路径查询

中文机器翻译题面 查看原题

分数: 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