Binary Lifting

def build_binary_lifting(n, parent, k):
    dp = [[-1] * (k+1) for _ in range(n+1)]
 
	# Recursion Approch
    # def binary_lifting(u, parent):
    #     dp[u][0] = parent
    #     for i in range(1, k+1):
    #         if dp[u][i-1] != -1:
    #             dp[u][i] = dp[dp[u][i-1]][i-1]
    #
    #     for v in tree[u]:
    #         if v == parent:
    #             continue
    #         binary_lifting(v, u)
    # binary_lifting(1, -1)
 
    for i in range(1, n+1):
        dp[i][0] = parent[i]
 
    for j in range(1, k+1):
        for i in range(1, n+1):
            if dp[i][j-1] != -1:
                dp[i][j] = dp[dp[i][j-1]][j-1]
 
    return dp
 
def find_kth_anc(dp, u, k):
    for i in range(len(dp[0]) -1, -1, -1):
        if k >= (1 << i):
            u = dp[u][i]
            if u == -1:
                return -1
            k -= (1<<i)
 
    return u
 
if __name__ == "__main__":
    n, q = map(int, input().split())
    
    from collections import defaultdict
 
    tree = defaultdict(list)
    parent = [-1] * (n+1)
 
    arr = list(map(int, input().split()))
    # Tree rooted at 1
    for u, v in enumerate(arr, 2):
        tree[u].append(v)
        tree[v].append(u)
        parent[u] = v
 
    dp = build_binary_lifting(n, parent, 20)
 
    for _ in range(q):
        node, k = map(int, input().split())
        print(find_kth_anc(dp, node, k))