P15262 [USACO26JAN2] The Chase G

Bessie 正在试图躲避农民们。农民们拥有 $N$（$2 \le N \le 5 \cdot 10^5$）个农场，其中从第 $i$ 个农场到第 $a_i$ 个农场有一条单向道路（$1 \le i \le N$，$a_i \neq i$）。共有 $F$（$1 \le F \le N$）个农民，第 $i$ 个农民最初驻扎在农场 $s_i$（$1 \le s_i \le N$，所有 $s_i$ 互不相同）。在每个时间步，每个农民都会从他们当前所在的农场出发，沿着道路移动到下一个农场。如果 Bessie 在任何时候与任意一个农民位于同一个农场，她就会被抓住。 假设 Bessie 从某个农场 $b$ 出发。在每个时间步，她有两个选择：她可以选择休息（停留在当前农场），或者选择沿着道路移动到下一个农场。如果她选择移动，她将与农民们同时移动。Bessie 的移动策略必须确保她在有限的时间步内永远不会被抓住。 对于每个起始农场 $b$（$1 \le b \le N$），求如果 Bessie 从农场 $b$ 出发，她最多可以选择休息多少次。

第一行包含两个整数 $N$ 和 $F$，分别表示农场的数量和农民的数量。 第二行包含 $N$ 个整数 $a_1 \ldots a_N$，表示从每个农场出发的单向道路通往的农场。 第三行包含 $F$ 个整数 $s_1 \ldots s_F$，表示每个农民的起始位置。

输出 $N$ 行，其中第 $b$ 行包含一个整数，表示如果 Bessie 从农场 $b$ 出发，她最多可以选择休息的次数。如果 Bessie 无法确保在有限的时间步内永远不会被抓住，则输出 $-1$。如果 Bessie 可以无限次休息，则输出 $-2$。

- 农场 1：如果 Bessie 从一个有农民的农场出发，那么她立即就会被抓住，因此输出 $-1$。 - 农场 2：Bessie 必须在每个时间步都选择移动，以避免被从农场 $1$ 出发的农民抓住。 - 农场 3-4：Bessie 可以无限次休息而不会被抓住。 ### 评分 - 输入 2：$N \le 50$ - 输入 3-10：$N \le 2000$ - 输入 11-20：无额外约束。 翻译由 DeepSeek 完成