An organization is modeled as a rooted tree with employees numbered 1 through n. The reporting structure is stored in a 0-indexed integer array parent of length n: parent[i] describes employee i + 1. If parent[i] is -1, employee i + 1 is the root; otherwise, parent[i] is that employee's direct manager. Every employee except the root has one manager and can have any number of direct reports.
When employee u sends a command, it reaches every descendant of u, but not u itself. At each employee, direct children are processed in increasing employee ID order. The command goes to the current child, the current child's entire subtree is handled under the same rule, and only then is the next child processed. This is equivalent to a depth-first preorder traversal of u's subtree with u omitted.
Given parent, u, and a 1-indexed integer k, return the ID of the k-th descendant that receives the command. Return -1 if u has fewer than k descendants.
Example 1:
Input: parent = [-1, 1, 1, 2, 2, 4], u = 1, k = 3
Output: 6
Explanation: The order from employee 1 is 2, 4, 6, 5, 3, so the third recipient is 6.
parent = [-1,1, 1, 2, 2, 4] u = 1 k = 3
6
Input: parent = [-1, 1, 1, 2, 2, 4], u = 1, k = 3. Employee 1 is the root.
Example 2:
Input: parent = [-1, 1, 1, 2, 2, 4], u = 2, k = 3
Output: 5
Explanation: The order from employee 2 is 4, 6, 5, so the third recipient is 5.
Example 3:
Input: parent = [-1, 1, 1, 2, 2, 4], u = 3, k = 2
Output: -1
Explanation: Employee 3 has no descendants, so there is no second recipient.
Constraints:
parent.length == nparent[i] is either -1 or an integer from to .parent is -1.parent = [-1,1, 1, 2, 2, 4] u = 1 k = 3
6
Input: parent = [-1, 1, 1, 2, 2, 4], u = 1, k = 3. Employee 1 is the root.