Question 03: ------------- You are given a forest (it may contain a single tree or more than one tree) with N nodes. Each node is given an integer value 0 to (N-1). You have to find: ================== Nearest common ancestor of two given nodes x1 and x2. N can be very large. Aim for an algorithm with a time complexity of O(N). INPUT FORMAT ------------- An integer T, denoting the number of testcases, followed by 3T lines, as each testcase will contain 3 lines. First line of each testcase has the value of N. Second line of each testcase has list of N values where the number at index i is the parent of node i. The parent of root is -1. ( The index has the range [0, N-1] ). Third line for each testcase contains two integers within the range of [0,N-1] whose common ancestor you have to find. OUTPUT FORMAT ============== For each testcase given, output a single line that has the nearest common ancestor to two given nodes x1 and x2. If a common ancestor is not present then output '-1'. SAMPLE INPUT ------------- 2 6 5 -1 1 1 5 2 0 3 13 4 3 -1 -1 1 2 7 3 1 4 2 1 2 8 5 SAMPLE OUTPUT ================ 1 -1
