Cơ quan Phát triển Khu vực của Liên Hợp Quốc (UNRDA) có một cơ cấu tổ chức được xác định rất rõ ràng. Cơ quan có tổng cộng \(N\) nhân viên, mỗi người đến từ một trong \(R\) khu vực địa lý khác nhau 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, trong đó nhân viên số \(1\), Chủ tịch, có thâm niên cao nhất. Các khu vực được đánh số từ \(1\) đến \(R\) theo thứ tự tùy ý. Mỗi nhân viên, trừ Chủ tịch, có đúng một cấp trên trực tiếp. Cấp trên trực tiếp luôn có thâm niên cao hơn những nhân viên dưới quyền trực tiếp của mình.

Ta nói nhân viên \(A\) là người quản lý của nhân viên \(B\) khi và chỉ khi \(A\) là cấp trên trực tiếp của \(B\), hoặc \(A\) là người quản lý của cấp trên trực tiếp của \(B\). Chẳng hạn, Chủ tịch là người quản lý của mọi nhân viên khác. Rõ ràng không thể có hai nhân viên là người quản lý của nhau.

Gần đây, Cục Điều tra Liên Hợp Quốc (UNBI) nhận được một số khiếu nại rằng cơ cấu tổ chức của UNRDA thiếu cân bằng và ưu ái một số khu vực hơn những khu vực khác. Để điều tra, UNBI muốn xây dựng một hệ thống máy tính nhận thông tin về cơ cấu cấp trên của UNRDA, rồi trả lời các truy vấn sau: với hai khu vực khác nhau \(r_1\) và \(r_2\), có bao nhiêu cặp nhân viên \((e_1,e_2)\) sao cho \(e_1\) đến từ khu vực \(r_1\), \(e_2\) đến từ khu vực \(r_2\), và \(e_1\) là người quản lý của \(e_2\)? Mỗi truy vấn có hai tham số \(r_1,r_2\) và kết quả là một số nguyên: số cặp nhân viên khác nhau thỏa mãn các điều kiện trên.

Cho khu vực quê quán của từng nhân viên và thông tin về cấp trên trực tiếp, hãy viết chương trình tương tác để trả lời các truy vấn như trên.

Dữ liệu vào

Trước tiên, đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(N\), \(R\), \(Q\), theo thứ tự này, cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả các nhân viên theo thứ tự thâm niên. Dòng thứ \(k\) trong số này mô tả nhân viên số \(k\). Dòng đầu tiên, mô tả Chủ tịch, chỉ chứa một số nguyên \(H_1\), là khu vực quê quán của Chủ tịch. Mỗi dòng còn lại chứa hai số nguyên cách nhau bởi một dấu cách: \(S_k\), số hiệu cấp trên trực tiếp của nhân viên \(k\), và \(H_k\), khu vực quê quán của nhân viên \(k\).

Tương tác

Sau khi đọc dữ liệu ban đầu, chương trình phải luân phiên đọc truy vấn từ đầu vào chuẩn và ghi câu trả lời ra đầu ra chuẩn. Phải trả lời lần lượt từng truy vấn trong số \(Q\) truy vấn: chương trình phải gửi câu trả lời cho truy vấn đã nhận trước khi có thể nhận truy vấn tiếp theo.

Mỗi truy vấn được đưa trên một dòng của đầu vào chuẩn, gồm hai số nguyên khác nhau \(r_1\) và \(r_2\), cách nhau bởi một dấu cách.

Dữ liệu ra

Với mỗi truy vấn, ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số cặp nhân viên \((e_1,e_2)\) của UNRDA sao cho khu vực quê quán của \(e_1\) là \(r_1\), khu vực quê quán của \(e_2\) là \(r_2\), và \(e_1\) là người quản lý của \(e_2\).

Dữ liệu bảo đảm rằng đáp án đúng cho mọi truy vấn được đưa trên đầu vào chuẩn luôn nhỏ hơn \(1\,000\,000\,000\).

Chú ý: Để tương tác đúng với chương trình chấm, bạn phải đẩy hết dữ liệu trong bộ đệm đầu ra chuẩn (flush) sau mỗi câu trả lời. Trong C hoặc C++ dùng scanf/printf, thực hiện fflush(stdout);; trong C++ dùng cin/cout, thực hiện cout << flush;; trong Pascal, thực hiện flush(output);.

Bạn cũng phải tránh làm chương trình bị chặn khi đọc đầu vào chuẩn. Khi dùng scanf, không kết thúc chuỗi định dạng bằng dấu cách hoặc ký tự xuống dòng: có thể dùng "%d", nhưng không dùng "%d " hay "%d\n". Chẳng hạn, lời gọi scanf("%d\n", &x) có thể khiến chương trình bị chặn. Các quy tắc này được trình bày trong tài liệu thông tin kỹ thuật của kỳ thi.

Ràng buộc

• \(1 \le N \le 200\,000\): số nhân viên.
• \(1 \le R \le 25\,000\): số khu vực.
• \(1 \le Q \le 200\,000\): số truy vấn chương trình phải trả lời.
• \(1 \le H_k \le R\) với \(1 \le k \le N\): khu vực quê quán của nhân viên \(k\).
• \(1 \le S_k < k\) với \(2 \le k \le N\): cấp trên trực tiếp của nhân viên \(k\).
• \(1 \le r_1,r_2 \le R\) và \(r_1 \ne r_2\): hai khu vực được hỏi trong một truy vấn.

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(30\) điểm thỏa mãn \(R \le 500\).

Một số bộ dữ liệu có tổng cộng \(55\) điểm thỏa mãn điều kiện không khu vực nào có quá \(500\) nhân viên.

Các bộ dữ liệu thỏa mãn cả hai điều kiện trên có tổng cộng \(15\) điểm.

Các bộ dữ liệu thỏa mãn ít nhất một trong hai điều kiện trên có tổng cộng \(70\) điểm.

Ví dụ

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

1
3
2
1

Nguồn

IOI 2009, ngày thi thứ hai: Regions, bản tiếng Anh 1.2. Tác giả đề bài: Long Fan và Richard Peng. Tập đề bài, thông tin kỹ thuật và lời giải IOI 2009.