Common manager: hints, no solution

A company has employees numbered 0 to n - 1. The array parents gives each employee's direct manager: parents[i] is the manager of employee i, and the single head of the company has parents[i] equal to -1. Managers can have any number of direct reports.

Employee m is a manager of employee e when m is e's direct manager or the manager of one of e's managers; nobody manages themselves. Given two employees a and b, return the nearest employee who is a manager of both of them, meaning the one deepest in the company. If a manages b, a still does not count, since nobody manages themselves, so look higher up. If a and b are the same person, that person's own manager is the answer. Return -1 when no such employee exists.

Examples

Input

parents = [-1, 0, 0, 1, 1, 2], a = 3, b = 4

Output

1

Note

Employees 3 and 4 both report directly to 1.

Input

parents = [-1, 0, 0, 1, 1, 2], a = 3, b = 1

Output

0

Note

Employee 1 manages 3 but not themselves, so the nearest shared manager is 0.

Constraints

• 1 <= n <= 2000
• parents describes exactly one tree with a single head
• 0 <= a, b < n

Hint 1: a nudge

If you list everyone above employee a, from the closest manager to the head, what would you look for while walking up from b?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing