CTDL> bài 18.A20 CTDL> bài [Graph].Kiểm tra đường đi.
[Graph].Kiểm tra đường đi.
Cho đồ thị vô hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Có Q truy vấn, mỗi truy vấn yêu cầu trả lời câu hỏi giữa 2 đỉnh s và t có tồn tại đường đi tới nhau hay không ?
Input Format
Dòng đầu tiên là 2 số n, m, tương ứng với số lượng đỉnh, cạnh của đồ thị. Các đỉnh của đồ thị được đánh số từ 1 tới n. m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị. Dòng tiếp theo là Q, Q dòng tiếp theo mỗi dòng chứa 2 đỉnh s, t cần truy vấn.(1<=s,t<=n<=1000; 1<=m<=n*(n-1)/2; 1<=Q<=10000)
Constraints
.
Output Format
Đối với mỗi truy vấn in ra 1 nếu có đường đi giữa s và t, ngược lại in ra -1.
Ví dụ:
Dữ liệu vào
6 8
3 4
2 6
4 6
2 3
3 5
4 5
6 3
4 2
6
4 1
6 6
3 6
1 3
1 5
2 6
Dữ liệu ra
-1
1
1
-1
-1
1
Comments