CSES - Forbidden Cities | Thành Phố Cấm

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

Có \(n\) thành phố và \(m\) con đường giữa chúng. Kaaleppi hiện đang ở thành phố \(a\) và muốn đi du lịch đến thành phố \(b\). Tuy nhiên, có một vấn đề: Kaaleppi gần đây đã cướp một ngân hàng ở thành phố \(c\) và không thể vào thành phố, bởi vì cảnh sát địa phương sẽ bắt được anh ta. Nhiệm vụ của bạn là kiểm tra xem có tuyến đường nào từ thành phố \(a\) đến thành phố \(b\) mà không đến thành phố \(c\) hay không.

Để bổ sung độ thách thức cho bài toán này, bạn phải xử lý \(q\) truy vấn trong đó \(a\), \(b\) và \(c\) khác nhau.

Input

Dòng đầu vào đầu tiên chứa ba số nguyên \(n\), \(m\) và \(q\): số thành phố, đường và truy vấn. Các thành phố được đánh số \(1, 2, \ldots, n\).

Sau đó, có \(m\) dòng mô tả các con đường. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một đường giữa thành phố \(a\) và \(b\). Mỗi con đường là hai chiều.

Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): có tuyến đường nào từ thành phố \(a\) đến thành phố \(b\) mà không đến thành phố \(c\) không?

Bạn có thể giả định rằng có một tuyến đường giữa hai thành phố bất kì.

Output

Đối với mỗi truy vấn, in YES nếu có một tuyến đường như vậy và NO nếu ngược lại.

Constraints

  • \(1 \leq n \leq 10 ^ 5\)
  • \(1 \leq m \leq 2 \cdot 10 ^ 5\)
  • \(1 \leq q \leq 10 ^ 5\)
  • \(1 \leq a, b, c \leq n\)

Example

Input:

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

Output:

YES  
NO  
YES

Bình luận


  • 0
    vanphukhang_0604    3:15 p.m. 26 Tháng 8, 2023 ← đã chỉnh sửa

    CSES - Forbidden Cities | Thành phố cấm

    Có \(n\) thành phố và \(m\) con đường giữa chúng. Kaaleppi hiện đang ở thành phố \(a\) và muốn đi du lịch đến thành phố \(b\). Tuy nhiên, có một vấn đề: gần đây Kaaleppi đã cướp một ngân hàng ở thành phố \(c\) và không thể đến thành phố này, vì cảnh sát địa phương sẽ bắt được anh ta. Nhiệm vụ của bạn là kiểm tra xem có tuyến đường nào từ thành phố \(a\) đến thành phố \(b\) mà không đi qua thành phố \(c\) hay không.

    Để bổ sung độ thách thức cho bài toán này, bạn phải xử lý \(q\) truy vấn với các thành phố \(a, b, c\) khác nhau.

    Input

    • Dòng đầu tiên chứa ba số nguyên \(n \ (1 \leq n \leq 10^5)\), \(m \ (1 \leq m \leq 2 \cdot 10^5)\), \(q \ (1 \leq q \leq 10^5)\): số thành phố, số con đường và số truy vấn. Các thành phố được đánh số \(1, 2, \ldots, n\).
    • \(m\) dòng tiếp theo mô tả các con đường, mỗi dòng chứa hai số nguyên \(a\) và \(b \ (1 \leq a, b, \leq n)\): có một con đường hai chiều nối hai thành phố \(a\) và \(b\).
    • \(q\) dòng cuối cùng mô tả các truy vấn, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c \ (1 \leq a, b, c \leq n)\): có tuyến đường nào đi từ thành phố \(a\) đến thành phố \(b\) mà không qua thành phố \(c\) hay không?
    • Dữ liệu đảm bảo rằng có một tuyến đường giữa hai thành phố bất kì.

    Output

    • Với mỗi truy vấn, in YES nếu có một tuyến đường thoả mãn, ngược lại in NO.

    Example

    Test 1

    Input 
    5 6 3
1 2
1 3
2 3
2 4
3 4
4 5
1 4 2
3 5 4
3 5 2
    Output 
    YES
NO
YES