족보 탐험

문제 정보

문제

촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되는 것을 기본으로 합니다. 두 사람의 촌수는 이 두 사람이 부모 자식 관계를 몇 번이나 따라가야 서로 연결되는가를 나타내지요. 예를 들어 형제자매는 같은 부모를 공유하기 때문에 2촌입니다. 조부모의 자식, 즉 부모의 형제자매는 이와 같은 원리로 3촌이지요.

어떤 가문의 족보가 시조부터 시작해 쭉 주어질 때, 두 사람의 촌수를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스는 한 가문의 족보와 촌수를 계산할 사람들의 쌍들로 구성됩니다.

각 테스트 케이스의 첫 줄에는 족보에 포함된 사람의 수 N (1 <= N <= 100,000) 과 촌수를 계산할 두 사람의 수 Q (1 <= Q <= 10,000) 가 주어집니다. 이 때 족보에 포함된 사람들은 0번부터 N-1 번까지 번호가 매겨져 있으며, 0번은 항상 이 가문의 시조입니다. 테스트 케이스의 두 번째 줄에는 N-1 개의 정수로 1번부터 N-1 번까지 각 사람의 아버지의 번호가 주어집니다. 그 다음 Q 줄에 각 2개의 정수로 두 사람의 번호 a, b 가 주어집니다. (0 <= a,b < N)

족보에는 시조의 후손이 아닌 사람은 주어지지 않으며, 자기 자신의 조상이 되는 등의 모순된 입력 또한 주어지지 않습니다.

입력의 크기가 크므로 가능한 빠른 입력 방법을 사용하는 것이 좋습니다.

출력

각 사람의 쌍마다 한 줄에 두 사람의 촌수를 출력합니다.

예제 입력

1
13 5
0 1 1 3 3 0 6 0 8 9 9 8
2 7
10 11
4 11
7 7
10 0

예제 출력

4
2
6
0
3

노트

다음 그림은 예제 입력을 나타낸 것입니다.

9개의 댓글이 있습니다.