Company Queries II

import sys


def main():
    data = map(int, sys.stdin.buffer.read().split())
    it = iter(data)
    n = next(it)
    q = next(it)
    bosses = [next(it) for _ in range(n - 1)]

    out = []
    app = out.append
    for _ in range(q):
        a = next(it)
        b = next(it)

        s = set()

        while a != 1:
            s.add(a)
            a = bosses[a - 2]

        while b != 1 and b not in s:
            b = bosses[b - 2]

        if b == 1:
            app("1")
        else:
            app(str(b))

    print("\n".join(out))


main()

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: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED