In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
The United Nations Regional Development Agency (UNRDA) has a very well defined organizational structure. It employs a total of people, each of them coming from one of geographically distinct regions of the world. The employees are numbered from to inclusive in order of seniority, with employee number , the Chair, being the most senior. The regions are numbered from to inclusive in no particular order. Every employee except for the Chair has a single supervisor. A supervisor is always more senior than the employees he or she supervises.
We say that an employee is a manager of employee if and only if is 's supervisor or is a manager of 's supervisor. Thus, for example, the Chair is a manager of every other employee. Also, clearly no two employees can be each other's managers.
Unfortunately, the United Nations Bureau of Investigations (UNBI) recently received a number of complaints that the UNRDA has an imbalanced organizational structure that favors some regions of the world more than others. In order to investigate the accusations, the UNBI would like to build a computer system that would be given the supervision structure of the UNRDA and would then be able to answer queries of the form: given two different regions and , how many pairs of employees and exist in the agency, such that employee comes from region , employee comes from region , and is a manager of . Every query has two parameters: the regios and ; and its result is a single integer: the number of different pairs and that satisfy the above-mentioned conditions.
Write a program that, given the home regions of all of the agency's employees, as well as data on who is supervised by whom, answers queries as described above.
- the number of employees
- the number of regions
- the number of queries your program will have to answer
- the home region of employee (for )
- the supervisor of employee (for )
- the regions inquired about in a given query
Your program must read from standard input the following data:
lines should be printed to the standard output, containing answers to subsequent queries. The response to each query must be a single line on standard output containing a single integer: the number of pairs of UNRDA employees and , such that 's home region is , 's home region is and is a manager of .
Note: The test data will be such that the correct answer to any query given on standard input will always be less than .
For a number of tests, worth a total of 30 points, will not exceed 500.
For a number of tests, worth a total of 55 points, no region will have more than 500 employees.
The tests where both of the above conditions hold are worth 15 points.
The tests where at least one of the two conditions holds are worth 70 points.
For the input data:
6 3 4 1 1 2 1 3 2 3 2 3 5 1 1 2 1 3 2 3 3 1
the correct result is:
1 3 2 1