| Submit | All submissions | Best solutions | Back to list |
POLQUERY - Police Query |
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. 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?
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?
Write a program that implements the described system.
Input
The first line contains two integers N and E (2 ≤ N ≤ 105, 1 ≤ E ≤ 5*105), the number of cities and roads. 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.
The following line contains the integer Q (1 ≤ Q ≤ 105), the number of queries the system is being tested on. 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.
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.
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.
The test data will be such that it is initially possible to get from each city to every other city.
Output
Output the answers to all Q queries, one per line. The answer to a query can be da (yes) or ne (no).
Example
Input:
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
Output:
da
da
ne
da
| Added by: | psetter |
| Date: | 2009-02-28 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | COI 08 |
hide comments
|
|||||
|
2023-02-16 06:26:22
pls give me the solution of this problem |
|||||
|
2021-08-08 19:08:40
if you think everything is right in your code then still your getting TLE then use scanf printf instead of cin,cout for fast process because my code was giving TLE because of that problem. |
|||||
|
2020-04-01 20:20:18
Those whose answer fails at 10th test case , consider what would happen if the edge is a bridge but there is no need to cross it to reach b from a. Similarly the case when vertex is an articulation point but there is no need to cross it to reach b from a. Its simply not on the path. |
|||||
|
2019-08-22 13:46:48
The sample case has 5 queries. sample output has 4 outputs. and the current order of output is wrong as well. The setter need to correct it. |
|||||
|
2019-07-02 20:46:34
@vishal yes mine is also failing at 10th test case. |
|||||
|
2018-03-23 09:30:10
can anyone tell me that after query of type 1 do we keep the baracades on the road that we didn't use and also if we remove c does this mean that c is removed permanenetly or just for that query it is not considered |
|||||
|
2016-07-06 01:10:13
yes @Youssef Ayman |
|||||
|
2016-06-09 17:40:22 Youssef Ayman
So should the output of the sample be da da da ne da ? |
|||||
|
2016-04-29 22:21:54
some issue with sample output |
|||||
|
2014-12-29 18:20:55 vishal
anyone with .wa on 10th case. |
|||||
RSS