Kth Node in Subtree Preorder

You are given a rooted tree of n nodes labeled 0 to n - 1, described by a 0-indexed integer array parent of length n, where parent[i] is the parent of node i and parent[root] = -1 for the single root. The array always forms a valid tree.

Visiting a node's subtree means starting at that node, then recursively visiting the subtree of each of its children, taking the children in ascending label order: a preorder traversal that always explores the smallest-labeled child first.

You are also given a 2D array queries, where queries[j] = [start, k]. For each query, find the k-th node visited when the traversal starts at node start (k = 1 is start itself). If the subtree of start contains fewer than k nodes, the answer is -1.

Return an integer array containing the answers in query order.

Examples

Example 1

Input: parent = [2,3,-1,0,5,2,4,5,0,3], queries = [[2,1],[0,4],[5,3]]
Output: [2,9,6]
Explanation: The root is node 2 (parent[2] = -1). Children in ascending order:
node 2 -> [0, 5], node 0 -> [3, 8], node 3 -> [1, 9], node 5 -> [4, 7], node 4 -> [6].
- [2,1]: the 1st node visited starting at the root is 2 itself.
- [0,4]: starting at node 0 the visit order is 0, 3, 1, 9, 8, so the 4th node is 9.
- [5,3]: starting at node 5 the visit order is 5, 4, 6, 7, so the 3rd node is 6.

Example 2

Input: parent = [2,3,-1,0,5,2,4,5,0,3], queries = [[3,1],[3,3],[3,4],[8,2]]
Output: [3,9,-1,-1]
Explanation: Same tree as Example 1. Starting at node 3 the visit order is
3, 1, 9, so the 1st node is 3, the 3rd is 9, and its subtree has only 3 nodes,
so there is no 4th node: -1. Node 8 is a leaf, so [8,2] is also -1.

Example 3

Input: parent = [-1], queries = [[0,1],[0,2]]
Output: [0,-1]
Explanation: A single-node tree: the traversal starting at node 0 visits only
node 0 itself.