You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

To help capture criminals on the run, the police are introducing a new computer system. The area covered by the police contains N cities and E bidirectional roads connecting them. The cities are labelled 1 to N.

为了帮助抓捕逃犯，警方引进了一套新的电脑系统。警察的辖区包含 $N$ 座城市和 $E$ 条双向道路，城市的编号是 $1\sim N$。

The police often want to catch criminals trying to get from one city to another. Inspectors, looking at a map, try to determine where to set up barricades and roadblocks. The new computer system should answer the following two types of queries:

警察常常要抓住那些逃往另一个城市的罪犯。侦查员看着地图，试着确定在哪里设置路障。新的计算机系统要回答以下两种问题：

1. Consider two cities A and B, and a road connecting cities G1 and G2. Can the criminals get from city A to city B if that one road is blocked and the criminals can't use it?

考虑城市 $A$ 和 $B$，以及连接城市 $G_1$ 和 $G_2$ 的道路。罪犯能否在那条路不通的情况下从 $A$ 逃到 $B$？

2. Consider three cities A, B and C. Can the criminals get from city A to city B if the entire city C is cut off and the criminals can't enter that city?

考虑三个城市 $A, B, C$。罪犯能否在无法通过 $C$ 的情况下从 $A$ 逃到 $B$?

Write a program that implements the described system.

写一个程序实现上述系统。

输入格式

The first line contains two integers N and E (2 ≤ N ≤ 100 000, 1 ≤ E ≤ 500 000), the number of cities and roads.

第一行两个整数 $N, E$（$2\leq N\leq 10 ^ 5$，$1\leq E\leq 5\times 10 ^ 5$），表示城市数量和道路数量。

Each of the following E lines contains two distinct integers between 1 and N – the labels of two cities connected by a road. There will be at most one road between any pair of cities.

接下来 $E$ 行，每行两个不同的数字 $u, v$，表示编号为 $u, v$ 的城市之间有一条道路。一对城市之间最多只有一条道路。

The following line contains the integer Q (1 ≤ Q ≤ 300 000), the number of queries the system is being tested on.

接下来一行，一个整数 $Q$（$1\leq Q\leq 3\times 10 ^ 5$），表示询问数量。

Each of the following Q lines contains either four or five integers. The first of these integers is the type of the query – 1 or 2.

接下来 $Q$ 行，每行四或五个整数描述一组询问。第一个数表示询问的类型 —— $1$ 或 $2$。

If the query is of type 1, then the same line contains four more integers A, B, G1 and G2 as described earlier. A and B will be different. G1 and G2 will represent an existing road.

如果询问类型为 $1$，那么在同一行还有四个整数 $A, B, G_1, G_2$。$A, B$ 不同，且 $G_1, G_2$ 之间存在道路。

If the query is of type 2, then the same line contains three more integers A, B and C. A, B and C will be distinct integers.

如果询问类型为 $2$，那么在同一行还有三个整数 $A, B, C$。$A, B, C$ 两两不同。

The test data will be such that it is initially possible to get from each city to every other city.

保证图中每两个点相互连通。

输出格式

Output the answers to all Q queries, one per line. The answer to a query can be "yes" or "no".

对于每组询问，输出 yes 或 no 表示回答。

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

yes
yes
yes
no
yes

提示

Croatian Olympiad in Informatics 2007 Task 2