Policija

题目描述

警方辖区包含 $N$ 座城市和 $E$ 条双向道路，城市编号为 $1\sim N$。保证任意两座城市之间都能互相到达。

系统需要回答两类询问：

1. 给定城市 $A,B$ 和一条连接 $G_1,G_2$ 的道路，若该道路无法通行，罪犯能否从 $A$ 到达 $B$？
2. 给定城市 $A,B,C$，若城市 $C$ 无法通过，罪犯能否从 $A$ 到达 $B$？

输入格式

第一行包含两个整数 $N,E$（$2\le N\le 10^5$，$1\le E\le 5\times 10^5$）。

接下来 $E$ 行，每行两个不同的整数 $u,v$，表示一条连接 $u,v$ 的双向道路。任意两座城市之间至多有一条道路。

接下来一行包含整数 $Q$（$1\le Q\le 3\times 10^5$）。

接下来 $Q$ 行，每行描述一组询问：

• 1 A B G1 G2：$A\ne B$，且 $G_1,G_2$ 之间存在道路；
• 2 A B C：$A,B,C$ 两两不同。

输出格式

对每组询问输出一行 yes 或 no。

样例输入 1

13 15
1 2
2 3
3 5
2 4
4 6
2 6
1 4
1 7
7 8
7 9
7 10
8 11
8 12
9 12
12 13
5
1 5 13 1 2
1 6 2 1 4
1 13 6 7 8
2 13 6 7
2 13 6 8

样例输出 1

yes
yes
yes
no
yes

数据范围

$2\le N\le 10^5$，$1\le E\le 5\times 10^5$，$1\le Q\le 3\times 10^5$。图为无重边、无自环的连通无向图。