#P10109. Supervisor Selection

    ID: 12094 Type: Default 1000ms 256MiB

Supervisor Selection

Supervisor Selection

There are \(N\) employees in a company, numbered from \(0\) to \(N-1\). Employee \(0\) is the boss. Every other employee \(i\) (with \(1 \le i \le N-1\)) has a direct supervisor \(f_i\). The management rule is defined recursively as follows:

[ \text{canManage}(x,y)=\begin{cases} \text{true} & \text{if } x=y,\ \text{true} & \text{if } y\neq 0 \text{ and } x=f_y,\ \text{true} & \text{if } y\neq 0 \text{ and } x \text{ can manage } f_y,\ \text{false} & \text{otherwise.} \end{cases} ]

Note: The boss (employee \(0\)) is special; he can only manage himself, i.e. even though he might appear in the supervisory chain of others, he is not allowed to manage any employee \(y\) with \(y\neq 0\).

Some colleagues want to cooperate and need to choose a host among themselves. The chosen employee \(x\) must be able to manage every participating colleague according to the rule above. If there are multiple suitable hosts, choose the employee with the largest number. If there is no such employee, output \(-1\).

inputFormat

The input consists of three parts:

  1. The first line contains two integers \(N\) and \(K\) where \(N\) is the total number of employees and \(K\) is the number of employees who wish to cooperate.
  2. The second line contains \(N-1\) space-separated integers: \(f_1, f_2, \dots, f_{N-1}\), where \(f_i\) is the direct supervisor of employee \(i\) (employee \(0\) has no supervisor).
  3. The third line contains \(K\) space-separated integers representing the IDs of the cooperating employees.

outputFormat

Output a single integer: the ID of the employee who can manage all the cooperating employees. If multiple employees satisfy the condition, output the one with the largest ID. If no such employee exists, output \(-1\).

sample

5 2
0 1 1 2
2 4
2