CSES - New Roads Queries | Truy vấn đường mới

Xem PDF



Tác giả:
Dạng bài
Điểm: 1900 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Ở đất nước Byteland\(N\) thành phố nhưng không có đường nào di chuyển giữa chúng. Tuy nhiên, mỗi ngày, một con đường mới sẽ được xây. Tổng cộng có \(m\) con đường.Trả lời \(q\) truy vấn: "Sau bao nhiêu ngày ta có thể di chuyển từ thành phố \(a\) sang \(b\)".

Input

  • Dòng đầu tiên chứa ba số nguyên \(N\), \(M\)\(Q\): số thành phố, con đường và truy vấn. Các thành phố được đánh số \(1, 2, \ldots, n\).
  • \(M\) dòng sau thể hiện con đường được xây dựng. Mỗi dòng chứa hai số nguyên \(a\)\(b\): có đường nối giữa \(a\)\(b\)
  • \(Q\) dòng cuối thể hiện mỗi truy vấn. Mỗi dòng gồm hai số nguyên \(a\)\(b\): muốn di chuyển từ thành phố \(a\) sang \(b\).

Output

  • Với mỗi truy vấn, in ra số ngày hoặc \(-1\) nếu không thể di chuyển.

Constraints

  • \(1 \ \leq \ N, M, Q \ \leq \ 2 \times 10^5\)
  • \(1 \ \leq a, b \ \leq \ n\)

Example

Sample input

5 4 3
1 2
2 3
1 3
2 5
1 3
3 4
3 5

Sample Output

2
-1
4

Bình luận

Không có bình luận nào.