class TreeAncestor:

    def __init__(self, n: int, p: List[int]):
        adj=self.adj=defaultdict(set)
        for i in range(n):
            adj[i].add(p[i])
            adj[p[i]].add(i)


        self.d=d={}
        d[1]=p[:]#storing height and parents respectively

        def height(u):
            q=deque()
            q.append(u)
            vis={u}
            ans=0
            while q:
                for _ in range(len(q)):
                    ans+=1
                    t=q.popleft()
                    for v in adj[u]:
                        if v not in vis:
                            vis.add(v)
                            q.append(v)
            return ans

        self.ht=ht=height(0)
        s=2
        while s<=ht:
            d[s]=[None]*n
            for i in range(n):
                first=d[s>>1][i]
                if first<0:
                    d[s][i]=-1
                else:
                    d[s][i]=d[s>>1][first]
            s=s<<1



        print(d)


    def getKthAncestor(self, node: int, k: int) -> int:
        d=self.d
        bins=bin(k)[2:][::-1]
        if k>self.ht:return -1

        for i,j in enumerate(bins):
            if j=='1':
                node=d[1<<i][node]


        return node