CSES - Reachability Queries | Truy vấn khả năng đi đến được

Xem PDF

Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một đồ thị có hướng gồm \(n\) nút và \(m\) cạnh. Các nút được đánh số \(1, 2, \ldots, n\).

Nhiệm vụ của bạn là trả lời \(q\) truy vấn có dạng "bạn có thể đi đến được nút \(b\) từ nút \(a\) không?"

Input

  • Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\)\(q\): số lượng nút, cạnh và truy vấn.
  • Sau đó, có \(m\) dòng mô tả các cạnh. Mỗi dòng có hai số nguyên riêng biệt \(a\)\(b\): có một cạnh từ nút \(a\) đến nút \(b\).
  • Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\)\(b\): "bạn có thể đi đến được nút \(b\) từ nút \(a\) không?"

Output

  • In đáp án cho từng truy vấn: YES hoặc NO.

Constraints

  • \(1 \leq n \leq 5 \cdot 10 ^ 4\)
  • \(1 \leq m, q \leq 10 ^ 5\)

Example

Sample input

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

Sample output

YES
NO
YES


Bình luận

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