Submit solution

Points: 1.63 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
IOI 2009 - Day 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cơ quan Phát triển khu vực Liên Hợp Quốc (UNRDA) có cơ cấu tổ chức rất rõ. Cơ quan này có tổng cộng ~N~ người, đến từ ~R~ vùng miền trên thế giới. Các nhân viên được đánh số từ ~1~ đến ~N~ theo thứ tự thâm niên. Với nhân viên số ~1~, chủ tịch, là người cao cấp nhất. Các khu vực được đánh số từ ~1~ đến ~R~. Mỗi nhân viên ngoại trừ chủ tịch đều có một giám sát viên duy nhất. Một giám sát viên luôn có thâm niên cao hơn các nhân viên mà anh ta hoặc cô ta giám sát.

Chúng ta hiểu rằng, một nhân viên ~A~ là quản lý của nhân viên ~B~ khi và chỉ khi ~A~ là giám sát của ~B~ hoặc ~A~ là quản lí của giám sát của ~B~. Như vậy, ví dụ như chủ tịch thì sẽ là người quản lý của tất cả các nhân viên khác.

Thật không may, cục điều tra Liên Hợp Quốc (UNBI) gần đây nhận được một số đơn khiếu nại rằng UNRDA có cơ cấu tổ chức mất cân bằng, ưu tiên một số khu vực trên thế giới hơn các khu vực khác. Để điều tra các cáo buộc, UNBI muốn xây dựng một hệ thống máy tính sẽ được cung cấp cấu trúc giám sát của UNRDA và sau đó có thể trả lời các truy vấn có dạng:

  • Đưa vào ~2~ khu vực ~r_1, r_2~ khác nhau tìm xem có bao nhiêu cặp nhân viên ~e_1, e_2~ của UNRDA, sao cho nhân viên ~e_1~ đến từ khu vực ~r_1~ và ~e_2~ đến từ ~r_2~ và ~e_1~ là quản lý của ~e_2~. Kết quả của nó là ~1~ số nguyên duy nhất.

Input

Dòng đầu tiên chứa 3 số nguyên ~N, R, Q~ lần lượt là số nhân viên của UNDRA, số khu vực và số lượng truy vấn.

Trong ~N~ dòng tiếp theo, dòng thứ ~k~ biểu diễn nhân viên thứ ~k~:

  • Dòng đầu chứa một số nguyên ~H_1~ là khu vực của chủ tịch.
  • Các dòng tiếp theo chứa hai số nguyên ~S_k, H_k~ lần lượt là thứ tự người giám sát và khu vực của nhân viên thứ ~k~.

Dòng thứ ~j~ trong ~Q~ dòng tiếp theo chứa 2 số nguyên ~r_1, r_2~ mô tả truy vấn thứ ~j~.

Output

In ra ~Q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Giới hạn

Trong tất cả các test có:

  • ~1 \leq N \leq 200000~
  • ~1 \leq R \leq 25000~
  • ~1 \leq Q \leq 200000~
  • ~1 \leq H_k \leq R \text{ } \left(1 \leq k \leq N\right)~
  • ~1 \leq S_k < k \text{ } \left(2 \leq k \leq N\right)~
  • ~1 \leq r_1, r_2 \leq R~

~30~ điểm ứng với các test có ~R \leq 500~.

~55~ điểm ứng với các test mà mỗi vùng không có quá 500 nhân viên.

Các test thỏa mãn cả 2 điều kiện trên có tổng ~15~ điểm

Các test thỏa mãn ít nhất một trong 2 điều kiện trên có tổng ~70~ điểm.

Sample Input

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

Sample Output

1
3
2
1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.