Nộp bài  Các bài nộp  Làm tốt nhất  Về danh sách bài 
NKPOLICE  Police 
English  Vietnamese 
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:
 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?
 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 ≤ 100 000, 1 ≤ E ≤ 500 000), 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 ≤ 300 000), 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 "yes" or "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 yes yes yes no yes
Được gửi lên bởi:  Jimmy 
Ngày:  20071227 
Thời gian chạy:  0.101s1s 
Giới hạn mã nguồn:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Ngôn ngữ cho phép:  Tất cả ngoại trừ: ERL GOSU JSRHINO NODEJS PERL6 PYPY RUST SED VB.NET 
Nguồn bài:  Croatian Open 2006 
hide comments


20210527 18:02:34
Tham khảo: https://vnspoj.github.io/problems/NKPOLICE 

20201022 10:30:55
nếu với đồ thị đó mà có 1 truy vấn là 1 2 8 1 10 thì phải xuất ra no chứ nhỉ :( 

20200611 15:35:28
LHP Nam Định chục đấm AC 

20191002 11:37:56
duonght_pro_xinhgainhathemattroi_:) 

20191002 10:09:41
http://ideone.com/hNgzyR 

20190918 09:30:51
xin chào lớp 11 tin THPT CHL :33 

20190917 15:58:47
Chào Hoàng Phi Hùng Tin K29 trường THPT Chuyên Hạ Long 

20190803 05:11:35
bài này 33.33 o do TLE đâu nhé 

20190801 08:07:51
AC EZ 

20180525 10:55:11
Last edit: 20190621 05:48:28 