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 G_{1} and G_{2}. 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 ≤ 10^{5}, 1 ≤ E ≤ 5*10^{5}), 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 ≤ 10^{5}), 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, G_{1} and G_{2} as described earlier. A and B will be different. G_{1} and G_{2} 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
hide comments
vinty:
20200401 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. 

nasif2587:
20190822 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. 

kanishk779:
20190702 20:46:34
@vishal yes mine is also failing at 10th test case. 

paroaro:
20180716 15:10:33
[deleted] Last edit: 20180716 15:10:51 

shahianshu:
20180323 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


linkret:
20160706 01:10:13
yes @Youssef Ayman 

Youssef Ayman:
20160609 17:40:22
So should the output of the sample be


glaurung_666:
20160429 22:21:54
some issue with sample output 

vishal:
20141229 18:20:55
anyone with .wa on 10th case. 

Hussain Kara Fallah:
20140208 05:04:48
I love this problem

Added by:  ~!(*(@*!@^& 
Date:  20090228 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  COI 08 