ACM 세포의 가계도
시간 제한2초메모리 제한512 MB
자손 수를 통해 번호 순서대로 가족 트리를 구성하고, 한 세포가 다른 세포의 조상인지 묻는 질의 중 참인 개수를 센다.
문제
과학자들은 새로 발견한 Agamic Cellular Microbe(ACM)의 행동을 연구하고 있다. 이 특별한 미생물은 짧은 시간에 스스로 대량으로 증식할 수 있다. ACM의 일생은 세 단계로 이루어진다.
- 출생 직후부터 대략 몇 초 동안 이어지는 유아기
- 단 몇 밀리초 만에 ACM 하나가 최대 100마리의 자손을 낳을 수 있는 증식기
- 남은 생애 동안 아무 활동도 하지 않는 성체기
실험 초기에 갓 태어난 ACM 세포 하나를 증식에 적합한 환경에 넣는다. 0번으로 번호가 붙은 이 세포가 증식을 시작하고, 그 자손들은 가계도에서의 위치에 따라 1번부터 번호가 붙는다. 실험 중에는 특수 장비를 사용해 각 ACM이 낳은 자손의 번호를 기록한다. 실험은 일정 시간이 지난 뒤 중단된다.
그림 1: 첫 번째 예제 입력에서 ACM들의 가계도
여러분의 과제는 어떤 ACM이 다른 ACM의 조상인지 판별하는 것이다.
입력
입력은 여러 테스트 케이스로 이루어진다. 입력의 첫 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 20)가 주어진다. T개의 테스트 케이스가 이어지며, 각 테스트 케이스 앞에는 빈 줄 하나가 있다.
각 테스트 케이스는 자손이 기록된 ACM의 수 N (1 ≤ N ≤ 300, 000)으로 시작한다. 이어지는 N개의 정수 Ci (0 ≤ i < N, 0 ≤ Ci ≤ 100)는 i번 ACM의 자손 수를 나타낸다. 이 정수들은 반드시 한 줄에 있지는 않다. 다음 줄에는 질의의 수 M (1 ≤ M ≤ 500, 000)이 주어진다. 이어서 M개의 줄에 서로 다른 두 정수 a와 b가 주어지며, a번 ACM이 b번 ACM의 조상인지 묻는다.
ACM의 전체 수는 N보다 클 수 있지만 2,000,000을 넘지 않는다.
출력
각 테스트 케이스마다 a번 ACM이 b번 ACM의 조상이라고 답해야 하는 질의의 수를 출력한다.