luogu#P4334. [COI2007] Policija

    ID: 8361 远端评测题 3000ms 63MiB 尝试: 4 已通过: 0 难度: 6 上传者: 标签>搜索图论2007深度优先搜索DFS割点COCI

[COI2007] Policija

题目描述

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.

为了帮助抓捕逃犯,警方引进了一套新的电脑系统。警察的辖区包含 NN 座城市和 EE 条双向道路,城市的编号是 1N1\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?

考虑城市 AABB,以及连接城市 G1G_1G2G_2 的道路。罪犯能否在那条路不通的情况下从 AA 逃到 BB

  1. 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,CA, B, C。罪犯能否在无法通过 CC 的情况下从 AA 逃到 BB?

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,EN, E2N1052\leq N\leq 10 ^ 51E5×1051\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.

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

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

接下来一行,一个整数 QQ1Q3×1051\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.

接下来 QQ 行,每行四或五个整数描述一组询问。第一个数表示询问的类型 —— 1122

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.

如果询问类型为 11,那么在同一行还有四个整数 A,B,G1,G2A, B, G_1, G_2A,BA, B 不同,且 G1,G2G_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.

如果询问类型为 22,那么在同一行还有三个整数 A,B,CA, B, CA,B,CA, 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".

对于每组询问,输出 yesno 表示回答。

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