Graph_hp

Trên bản đồ thành phố HP có \(n\) địa điểm chiến lược (đánh số từ 1 đến \(n)\) và \(m\) con đường hai chiều (đánh số từ 1 đến \(m)\), con đường \(i\ (1 \leq i \leq m)\) nối giữa hai địa điểm \(x_{i}\) và \(y_{i}\ (1 \leq x_{i},y_{i} \leq n)\).

Có \(q\) truy vấn, truy vấn thứ \(i\ (1 \leq i \leq q)\) cho hai số \(l\) và \(r\), bạn hãy cho biết mọi cặp địa điểm chiến lược có thể di chuyển được với nhau không nếu chỉ dùng các con đường \(l,l + 1,\ldots,r.\)

Dữ liệu:

+ Dòng đầu tiên gồm hai số nguyên dương \(n,m\ (2 \leq n \leq 100;1 \leq m \leq 100.000);\)

+ \(m\) dòng sau, dòng thứ \(i\ (1 \leq i \leq m)\) gồm hai số nguyên dương \(x_{i},y_{i}\) \((1 \leq x_{i},y_{i} \leq n)\) mô tả một con đường nối giữa hai địa điểm \(x_{i}\) và \(y_{i}\);

+ Dòng tiếp theo chứa số nguyên dương \(q\ (1 \leq q \leq 100.000)\);

+ \(q\) dòng sau, dòng thứ \(i\ (1 \leq i \leq q)\) gồm hai số nguyên \(l\) và \(r\) mô tả truy vấn \(i\) \((1 \leq l \leq r \leq m)\);

Kết quả: Ghi \(q\) dòng, dòng thứ \(i\) in ra “Yes” nếu mọi cặp địa điểm chiến lược có thể đến được nhau và “No” nếu ngược lại.

Ràng buộc:

+ 20% số điểm thoả mãn: \(m,q \leq 100\);

+ 20% số điểm tiếp theo thoả mãn: \(l = 1,\ \forall i \in \lbrack 1;q\rbrack\);

+ 20% số điểm tiếp theo thoả mãn: \(l \leq 50,\ \forall i \in \lbrack 1;q\rbrack\);

+ 40% số điểm còn lại không có ràng buộc gì thêm.

Ví dụ:

Input	Output	Giải thích
4 6 1 2 2 3 3 4 4 1 1 3 2 3 2 1 3 3 5	Yes No	- Ở truy vấn đầu tiên, các con đường có thể sử dụng là (1, 2), (2, 3), (3, 4). Tất cả 4 địa điểm chiến lược đều có thể đến được với nhau; - Ở truy vấn thứ hai, các con đường có thể sử dụng là (3, 4), (4, 1), (1, 3). Các địa điểm 1, 3, 4 có thể đến được với nhau, tuy nhiên địa điểm 2 lại bị cô lập.