You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves).

The cells are named with an integer value from 0 to

N-1.

You have to find:

Nearest meeting cell: Given any two cells – C1, C2, find the closest cell Cm that can be reached from both

C1 and C2.

INPUT FORMAT

- An integer T, denoting the number of testcases, followed by 3T lines, as each testcase will contain 3 lines.
- The first line of each testcase has the number of cells N
- The second line of each testcase has a list of N values of the edge[] array. edge[i] contains the cell number that can be reached from cell ‘i’ in one step. edge[i] is -1 if he ‘i’th cell doesn’t have an exit.
- Third line for each testcase contains two cell numbers whose nearest meeting cell needs to be found. (return-1 if there is no meeting cell from the two given cells)

OUTPUT FORMAT

For each testcase given, output a single line that denotes the nearest meeting cell (NMC)

Sample Input & Output

Input

1

23

4 4 1 4 1 3 8 8 8 0 8 1 4 9 15 11-1 10 15 22 22 22 22 22 21

9 2

Output: 4

How to solve this question in C++.

Here is the code for python: Nearest meeting cell – Ask python questions