贝尔兰发生革命后,新独裁者面临着意想不到的挑战:必须以某种方式统治这个国家。独裁者是一个非常高效的管理者,但他不能亲自向每一个公民发号施令。这就是为什么他决定挑选一些他可以控制的领导人。这些领导人将直接向公民发出命令。然而,领导效率因人而异(即,虽然 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 位于不同的连通分量中,它们之间没有路径。