Bessie is trying to evade the farmers. The farmers own N (2≤N≤5⋅105) farms with a one way road between the i-th farm and the ai-th farm (1≤i≤N, ai≠i). There are F (1≤F≤N) farmers and the i-th farmer is initially stationed at farm
si(1≤si≤N, all si unique). At each time step, every farmer takes the road at their current farm and moves to the next. Bessie gets caught if she is ever located at the same farm as any farmer.
Suppose Bessie starts at some farm b. At each time step, she has two options: she can either choose to rest (stay at her current farm) or take the road and move to the next farm. If she chooses to move, she moves simultaneously with the farmers. Bessie moves so that she is never caught by any farmer in a finite number of timesteps.
For each starting farm b (1≤b≤N), find the maximum number of times Bessie can choose the rest option if she starts at farm b.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and F, the number of farms and the number of farmers.
The second line contains a1…aN, the one-way roads going out of each farm.
The third line contains s1…sF, the starting locations of each farmer.
OUTPUT FORMAT (print output to the terminal / stdout):
Output N lines, the b-th of which must consist of a single integer denoting the maximum number of times Bessie can choose the rest option if she starts at farm b. If there is no way for Bessie to ensure she is never caught after a finite number of timesteps, then output −1. If Bessie can rest an infinite number of times, then output −2.
SAMPLE INPUT:
4 1
2 1 4 3
1
SAMPLE OUTPUT:
-1
0
-2
-2
Farm 1: If Bessie starts at a farm with a farmer, then she is caught immediately, and you should output −1.
Farm 2: Bessie must choose to move at every timestep to avoid being caught by the farmer who starts at farm 1.
Farms 3-4: Bessie can rest an infinite number of times without being caught.
SCORING:
Input 2: N≤50
Inputs 3-10: N≤2000
Inputs 11-20: No additional constraints.
Problem credits: Alex Liang