Description
In a tree data structure where each node points to its parent, the lowest common ancestor of A an B can be easily determined by finding the first intersection of the paths from A and B to the root.
Given a rooted tree, please output the lowest common ancestor for each query.
For example, the lowest common ancestor of A and B is C.
Input
The first line contains a positive integer T (T <= 40), which indicates how many cases in the input. For each case, the first line contains a positive integer N, denoting the amount of node in the tree (labeled from 1 to N). The second line contains exactly N numbers. The first number denotes the parent of node 1, and the second number denotes the parent of node 2 ..., etc. The parent of the root will be labeled as -1.
Then multiple queries (query < 100) follow. Each line contains two positive integers A and B. The query is terminated by two zeros.
Each case is separated by a blank line.
Case 1: 1 <= N <= 10
Case 2: 1 <= N <= 100
Case 3: 1 <= N <= 1000
Case 4: 1 <= N <= 100000
Output
For each case a line, print the case number first, then output the node number of the least common ancestor for each query. Each answer should be separated by a single space.