## COI '06 #2 Policija

View as PDF

Points: 17 (partial)
Time limit: 1.4s
Memory limit: 64M

Problem type

To help capture criminals on the run, the police are introducing a new computer system. The area covered by the police contains cities and bidirectional roads connecting them. The cities are labelled to .

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 and , and a road connecting cities and . Can the criminals get from city to city if that one road is blocked and the criminals can't use it?
2. Consider three cities , and . Can the criminals get from city to city if the entire city is cut off and the criminals can't enter that city?

Write a program that implements the described system.

#### Input Specification

The first line contains two integers and , the number of cities and roads.

Each of the following lines contains two distinct integers between and – 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 , the number of queries the system is being tested on.

Each of the following 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 , then the same line contains four more integers , , and as described earlier. and will be different. and will represent an existing road.

If the query is of type , then the same line contains three more integers , and . , and 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 Specification

Output the answers to all queries, one per line. The answer to a query can be yes or no.

Note: if your program correctly answers all questions of one type but not the other, it will receive 50% of the score for that case. Even then your program needs to answer all queries (the other queries can be answered arbitrarily).

#### Sample 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

#### Sample Output

yes
yes
yes
no
yes