class TreeAncestor {
public:
    int power_of_two;
  vector<vector<int>> upper_node;
  vector<int> depth_of_node;
    TreeAncestor(int n, vector<int>& parent) {
        power_of_two = 0;
        while((1 << power_of_two) <= n) {
            power_of_two++;
        }
        depth_of_node.resize(n + 1, 0);
        upper_node.resize(n);
        for(int i = 0; i < n; i++) {
            upper_node[i].resize(power_of_two + 1, 0);
        }
     
        parent[0] = 0;
        for(int i = 0; i < n; i++) {
            upper_node[i][0] = parent[i];
            if(i != 0) {
                depth_of_node[i] = depth_of_node[parent[i]] + 1;
            }
            
            for(int j = 1; j < power_of_two; j++) {
                upper_node[i][j] = upper_node[ upper_node[i][j - 1] ][j - 1];
            }
            
        }
        
    }
    
    int getKthAncestor(int node, int k) {
        if(depth_of_node[node] < k) {
            return -1;
        }
        int result = node;
        for(int i = 0; i < power_of_two; i++) {
            if(k & (1 << i)) {
                result = upper_node[result][i];
            }
        }
        return result;
    }
};