样例下载

题目描述

你正在玩一个密室逃脱游戏。

有 N 个密室，编号为 1 ~ N。

每个密室有且仅有一条通往另一个密室的单向道路。密室 $i$ 通往的是密室 $T_i$。（$1 ≤ i, T_i ≤ N; T_i≠i$）

有 M 个敌人正在对你进行抓捕。这些敌人编号为 1 ~ M，其中编号为 i 的敌人现在正位于编号为 $S_i$ 的密室中。（$1 ≤ i ≤ M ≤ N; 1 ≤ S_i ≤ N;$ 所有 $S_i$ 两两不同，即开始时不会有两个敌人位于同一个密室中。）

你现在正位于编号为 $x$ 的密室中。在你开始逃脱的瞬间，所有敌人立即开启了抓捕行动。

敌人们一直在移动。每一分钟，每个敌人都会从所在密室沿着有向道路到达下一个密室。

同样的，每一分钟，你可以从所在密室沿着有向道路到达下一个密室。但你也可以选择休息，则这一分钟，你会待在所在密室不动。

在任意时刻，如果你和任意一个敌人位于同一个密室，则你将被抓住。

为了不被敌人抓住，你最多可以休息几分钟？

你需要输出当 $x=1, 2, ……, N$ 时的 $N$ 个答案。如果你一定会被敌人抓住，则输出 -1; 如果你无论休息多久，都不会被敌人抓住，则输出 -2; 否则，输出你最多可以休息的分钟数。

输入格式

第一行：两个整数 $N, M$

第二行：$N$ 个整数 $T_i$

第三行：$M$ 个整数 $S_i$

输出格式

共 $N$ 行，依次表示当 $x=1, 2, ……, N$ 时答案。

输入样例

4 1
2 1 4 3
1

输出样例

-1
0
-2
-2

样例解释

• x=1：你和敌人同在密室 1，则你立刻被抓住。
• x=2：你必须不停逃跑，一刻也不能休息。
• x=3, 4：你无论休息多久也不可能被抓住。

数据范围

• 10% 的数据：$N ≤ 50$
• 30% 的数据：$N ≤ 2000$
• 100% 的数据：$2 ≤ N ≤ 5 · 10^5$