United Nations Regional Development Agency (UNRDA) 는 매우 잘 조직된 기구이다. 이 기구는 총 N 명의 직원을 두고 있고 각각은 세계에서 지리적으로 유일한 지역으로 부터 온 사람이다.

직원들은 연장자 순으로 1 부터 N 까지 순차적으로 번호를 부여되어 있다. 1 번 직원이 의장이고 가장 연장자이다. 지역은 1 에서 R 까지 임의의 순으로 변호가 부여되어 있다.

의장을 제외한 모든 직원은 한 사람의 상관을 가진다. 상관은 항상 더 상관이다 그가 지도하는 직원보다

A 가 B 의 상관이면 B 는 A 의 부하직원이다. 예를 들어 의장은 모든 직원의 매니저이다. 또한 어떤 두 직원도 다른 직원의 매니저가 될수 없다.

불행하게도 , 이 기구는 최근 많은 불평을 받았다. 직원이 지역의 균등하게 있지않고 한 지역에서 치중되어 있다고.

이를 조사하기 위하여 기구는 컴퓨터 시스템을 구축해서 이 기구의 조직도를 주고 다음 폼의 질의에 응답 할 수 있는 두 개의 다른 지역 r1,r2 를 주고 직원 e1,e2 의 쌍이 이 조직에 얼마나 많은 가를 e1 은 r1 지역 출신이고 , e2 는 r2 의 지역출신이고 , e1 이 e2 의 상관이다.

모든 질의는 두 파라미터 r1 , r2를 가진다. 결과는 정수 하나로 위 조건을 만족하는 다른 쌍의 e1 과 e2 의 수이다.

제한

• 1 <= N <= 200,000 직원 수
• 1 <= R <= 25,000 지역 수
• 1 <= Q <= 200,000 질의 수
• 1 <= Hk <= R T 직원의 홈 지역의 수 (for 1 <= k <= N)
• 1 <= Sk < k 직원 k 의 상관 수 (for 2 <= k <= N)
• 1 <= r1, r2 <= R 질의에 사용된 r1,r2

입력

• 첫 라인에는 N,R,Q 가 주어진다. 차례대로 N 은 직원 수 , R 은 지역수 , Q 는 질의 수 이다.
• 다음 N 라인에는 기구의 N 명의 정보가 상관부터 주어진다. k 번째는 k 번째 직원의 정보이다.
  • 이 라인의 첫수는 (의장을 나타내는) 정수 하나가 주어진다. 의장의 홈 지역 H1 이다.
  • 다음 N -1 라인은 두 수가 주어진다. k 번째 직원의 상관 Sk 와 이 직원의 홈 지역 Hk 이다.
• 다음 Q 개의 질의가 주어진다.

출력

NOTE: The test data will be such that the correct answer to any query given on standard input will always be less than 1,000,000,000.

입출력 예

입력

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 

입출력 보충

출처: International Olympiad In Informatics 2009