POLQUERY - Police Query

no tags 

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

hide comments
linkret: 2016-07-06 01:10:13

yes @Youssef Ayman

Youssef Ayman: 2016-06-09 17:40:22

So should the output of the sample be
da
da
da
ne
da
?

glaurung_666: 2016-04-29 22:21:54

some issue with sample output

vishal: 2014-12-29 18:20:55

anyone with .wa on 10th case.

Hussain Kara Fallah: 2014-02-08 05:04:48

I love this problem
It is perfect

Zhouxing Shi: 2013-04-09 01:49:13

@Abir YES!! And the problem is really nice!!

Last edit: 2013-04-09 04:58:59
Ja Issa Tai: 2012-11-12 08:48:31

sample input contains 5 queries, sample output contains only 4?

~!(*(@*!@^&: 2009-05-28 20:04:50

da = yes, ne = no

[Trichromatic] XilinX: 2009-05-28 20:04:50

The output (in your submitted program) must be "da" or "ne" (don't mind the sample).

Edit: Q is less than 300000 (not 100000).

Last edit: 2009-05-21 03:18:14
Abir: 2009-05-28 20:04:50

Resource should be COI 07.


Added by:~!(*(@*!@^&
Date:2009-02-28
Time limit:0.121s-0.487s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:COI 08