← 返回题目列表

Codeforces · 97/E

E. 领导者

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

贝尔兰发生革命后,新独裁者面临着意想不到的挑战:必须以某种方式统治这个国家。独裁者是一个非常高效的管理者,但他不能亲自向每一个公民发号施令。这就是为什么他决定挑选一些他可以控制的领导人。这些领导人将直接向公民发出命令。然而,领导效率因人而异(即,虽然 A 是一位高效的领导者,但 B 可能不那么擅长)。这就是独裁者向世界著名的伯兰科学家寻求帮助的原因。科学家们提出了一种创新技术——让领导者两人一组工作。

关系图是一些无向图,其顶点对应于人。简单路径是没有重复顶点的路径。长期且昂贵的研究表明,如果关系图中的两个人之间有一条带有奇数条边的简单路径,那么他们就具有最高的领导素质。科学家们决定将这样的不同人对称为“领导者对”。特勤局为科学家提供了关系图,因此任务很简单——我们必须学会告诉独裁者给定的对是否是领导对。帮助科学家应对任务。

输入

第一行包含整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — 关系图中相应的顶点和边的数量。接下来的 m 行包含整数对 a 和 b,这意味着第 a 和第 b 个顶点之间有一条边(顶点从 1 开始编号,1 ≤ a,b ≤ n)。保证图没有环或重边。

下一行包含数字 q (1 ≤ q ≤ 105) — 科学家感兴趣的对的数量。接下来的 q 行包含这些对(与边的格式相同,查询可以重复,查询可以包含一对相同的顶点)。

输出

对于每个查询,如果两人之间存在简单的奇数路径,则在单行上打印“是”;否则,打印“否”。

示例

输入 #1

7 7
1 3
1 4
2 3
2 4
5 6
6 7
7 5
8
1 2
1 3
1 4
2 4
1 5
5 6
5 7
6 7

输出 #1

No
Yes
Yes
Yes
No
Yes
Yes
Yes

注意

样品注释:

1) 在顶点 1 和 2 之间总共有 2 条不同的简单路径:1-3-2 和 1-4-2。它们都由偶数条边组成。

2) 顶点 1 和 3 由一条边连接,这就是为什么它们的简单奇数路径是 1-3。

5) 顶点 1 和 5 位于不同的连通分量中,它们之间没有路径。