Problem E
Easygoing Workplace
In the company "Work Life Balance", there are $N$ employees numbered 1 to $N$, where employee 1 is the CEO of the company, and for $2 \leq i \leq N$, employee $i$ has a direct superior $B_i$. For two employees $a, b$, we say that employee $b$ is a subordinate of employee $a$ if and only if there exists a positive integer $k \geq 2$ and a sequence $u_1 = b, u_2, \dots , u_k = a$ such that for each $1 \leq i \leq k - 1$, employee $u_{i + 1}$ is the direct superior of employee $u_i$. Each employee also has a work tolerance level $A_i$.
Every day, the $N$ employees will go to the office in some order. When employee $i$ gets to work, if he sees that at most $A_i$ of his subordinates are doing work, he will do work as well. Otherwise, he will sit in the office and slack off. One day, the CEO of the company felt like maintaining a balance of work and slacking at the workplace, so he wonders if the $N$ employees could come to the office in some order such that exactly $K$ of them do work. Please help him find such an order, or determine that it is impossible.
Input
The first line of input contains an two integers $N, K$ $(1 \leq N \leq 5 \cdot 10^5, 0 \leq K \leq N)$, the number of employees and the target number of employees doing work.
The second line of input contains $N$ integers $A_1, A_2, \dots , A_N (0 \leq A_i \leq N - 1)$.
The third line of input contains $N - 1$ integers $B_2, B_3, \dots , B_N (1 \leq B_i < i)$.
Output
If it is not possible to find an order for the employees to go to the office such that exactly $K$ of them do work, output $-1$.
Otherwise, output a permutation of integers from 1 to $N$, $P_1, P_2, \dots , P_N$ in a single line, separated by spaces, such that if the employees go to office in the order $P_1, P_2, \dots , P_N$, exactly $K$ of them will be doing work. If there are multiple solutions, output any of them.
Sample Input 1 | Sample Output 1 |
---|---|
5 3 3 2 1 2 2 1 2 2 1 |
-1 |
Sample Input 2 | Sample Output 2 |
---|---|
7 5 4 2 0 0 3 0 1 1 2 1 2 2 3 |
7 3 6 5 2 1 4 |