Company Queries II

n,q = map(int, input().split())
p = [0, 1] + list(map(int,input().split()))

d = [0]*(n+1)
for i in range(2, n + 1):
    d[i] = d[p[i]] + 1

L = max(1, n.bit_length())
up = [p]

for k in range(1, L):
    t = up[-1]
    row = [0] * (n+1)

    for i in range(1, n+1):
        row[i] = t[t[i]]

    up.append(row)


for i in range(q):
    a, b = map(int, input().split())

    if d[a] < d[b]:
        a,b = b,a

    diff = d[a]-d[b]
    for k in range(L):

        if diff >> k & 1:
            
            a = up[k][a]

    if a != b:
        for k in range(L-1, -1,-1):

            if up[k][a] != up[k][b]:

                a,b = up[k][a],up[k][b]

        a = p[a]

    print(a)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED