问题 A: 大雪封路

内存限制:256 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:99 解决:17

题目描述

小玉的城市正在遭遇一场猛烈的暴风雪,城市的一切都被笼罩在白茫茫的雪景中。

小玉所在的城市可以看作是一张 $N$ 个顶点,$M$ 条边的无向连通图。每个顶点有从 $1$ 到 $N$ 的编号,每条边都是连接着两个不同顶点的双向道路。初始时,所有顶点都是没有积雪的状态。随着暴风雪越下越大,不断有消息传出某个顶点被积雪覆盖住了。小玉家的车有着很强的越野性能,可以在积雪上行驶。但连续涉雪行驶是十分危险的,所以他不能开车从一个被雪覆盖的顶点开向另一个被雪覆盖的顶点。

尽管天气十分恶劣,小玉还是想出门逛一逛。他想看看这场暴风雪给城市带来了什么样的变化,也想找找有没有什么有趣的事情发生。从现在开始有 $Q$ 次事件。每次事件有两种情况。情况 1 是某个顶点 $u$ 被雪覆盖了;情况 2 是小玉想知道他能否从某个顶点 $u$ 前往另一个顶点 $v$。

输入

输入的第一行包含两个整数 $N, M(2\leq N, M \leq 2 \times 10^5)$,表示小玉所在城市的顶点和边的个数。

接下来 $M$ 行,每行包含两个整数 $u, v(1\leq u, v\leq N)$,代表顶点 $u$ 和 $v$ 之间存在着一条双向道路

接下来一行是一个整数 $Q (1 \leq Q \leq 2 \times 10^5)$,代表接下来会发生 $Q$ 次事件。

接下来 $Q$ 行,每行代表一次事件。

事情可能为以下两种:
  • $1$ $u$ - 代表顶点 $u$ 被雪覆盖了。
  • $2$ $u$ $v$ - 代表小玉想知道他能否从顶点 $u$ 前往顶点 $v$。
保证初始状态时小玉的城市是一张不存在自环和重边的无向连通图。保证每个事件中 $1 \leq u, v \leq N, u \neq v$。保证每个顶点只存在一次事件1。保证至少有一次事件2。

输出

对于每个事件2,如果小玉能从顶点 $u$ 前往顶点 $v$,输出一行"Yes",否则输出一行"No"(不含引号)。

样例输入 复制

5 4
2 1
2 3
1 4
1 5
5
2 3 5
1 1
2 3 5
1 2
2 3 5

样例输出 复制

Yes
Yes
No