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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.