문제
훌륭한 자연경관을 가지고 있어서 관광객이 많이 오는 A산에 강이 흐르는데, 강줄기에 N개의 시설이 있다. (강줄기가 갈라져 있을 수 있다.)
이 시설들을 편의상 1번~N번으로 번호를 붙이자.
각각의 시설들은 총 F가지(식당, 생태체험관 등등)의 특징으로 분류된다.
A산의 관광 컨텐츠를 개발하는 담당을 맡은 지헌이는 강줄기를 따라 래프팅을 하면서 이동하는 방식의 새로운 이동수단을 개발했다.
지헌이의 아이디어가 A산에 적용되었다.
하지만 강물은 위에서 아래로만 흐르기 때문에 한 시설에서 래프팅 보트를 타면 무조건 특정한 다른 시설로 가게 된다.
단, 1번 시설은 강의 최하류에 위치해 있기 때문에 1번 시설에서는 어디로도 더 이상 갈 수 없고, 또한 어떤 시설에서도 1번 시설로 갈 수 있다.
요즘 들어서 여행 계획을 짜는 사람들이 많아지고 있는데, M명의 사람들은 각각 특징이 Si인 시설에서 특징이 Ei인 시설로 가고 싶어한다.
A산의 강줄기가 상당히 복잡하기 때문에, 지헌이는 특징이 Si인 시설에서 특징이 Ei인 시설로 갈 수 있는 방법의 수를 계산하는 것에 무리가 생겼고,
프로그래머인 당신에게 이를 계산하는 프로그램을 짜달라고 부탁을 하였다.
입력
첫 번째 줄에는 N(1≤N≤200,000), F(1≤F≤25,000), M(1≤M≤200,000)이 주어진다.
두 번째 줄에는 1번 시설의 특징이 주어지고, 그 다음 N-1개의 줄에는 k번 시설에서 래프팅 보트를 타면 가게 되는 다른 시설의 번호와 k번 시설의 특징이 주어진다.
그 다음 M개의 줄에는 Ei와 Si가 주어지는데, Ei가 먼저 입력된다는 것에 유의해라.
출력
M개의 줄에 각각 Si번 시설에서 Ei번 시설로 가는 방법의 수를 출력한다.
예제1
735
3
11
22
22
12
53
31
21
12
31
32
13
1
2
2
3
0