Company Queries II

n, q = [int(x) for x in input().split()]

GRAPH = {i:[] for i in range(n+1)}
for i, x in enumerate(input().split()):
    x = int(x)
    GRAPH[i+2].append(x)
    GRAPH[x].append(i+2)

dfs_res = []

def dfs(node):
    visited = set()
    to_visit = [node]
    depth = 1
    while len(to_visit) > 0:
        node = to_visit.pop()
        visited.add(node)
        dfs_res.append((node, depth))
        if len(GRAPH[node]):
            next_node = GRAPH[node].pop()
            if next_node in visited:
                depth -= 1
            else:
                depth += 1
            to_visit.append(next_node)

dfs(1)

def find_index(node):
    for i, tupl in enumerate(dfs_res):
        if tupl[0] == node:
            return i

sol = []
for _ in range(q):
    a, b = [int(x) for x in input().split()]
    index_a = find_index(a)
    index_b = find_index(b)
    sol.append(min(dfs_res[min(index_a, index_b):max(index_a, index_b)+1], key=lambda x: x[1])[0])

for elt in sol:
    print(elt)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED