Description

有 $n$ 个（编号从 $1$ 到 $n$）人预约了医生的门诊。医生必须选择这些人预约的顺序。第 $i$ 位患者应该在前 $p_i$ 位人中被预约。还有 $m$ 个限制，格式如下：第 $i$ 个a限制由两个整数 $(a_i, b_i)$ 表示，意味着索引为 $a_i$ 的患者应该在索引为 $b_i$ 的患者之前被预约。

例如，如果 $n = 4$、$p = [2, 3, 2, 4]$、$m = 1$、$a = [3]$ 和 $b = [1]$，那么不违反限制的患者预约的唯一顺序是 $[3, 1, 2, 4]$。对于 $n =3$、$p = [3, 3, 3]$、$m = 0$、$a = []$ 和 $b = []$，任何预约顺序都是有效的。

对于每位患者，计算在所有不违反限制的可能顺序中，他们可以拥有的最小位置。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2000$; $0 \le m \le 2000$）。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。

然后跟随 $m$ 行。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$; $a_i \ne b_i$）。所有的 $(a_i, b_i)$ 对都是不同的（即如果 $i \ne j$，那么要么 $a_i \ne a_j$，要么 $b_i \ne b_j$，或者两者都成立）。

输入的额外约束：至少有一种有效的患者预约顺序。

Output

打印 $n$ 个整数，其中第 $i$ 个整数等于第 $i$ 位患者在所有有效顺序中的最小位置。顺序中的位置从 $1$ 到 $n$ 编号。

4 1
2 3 2 4
3 1

3 0
3 3 3

5 3
4 3 3 2 5
3 1
1 5
4 2

2 3 1 4

1 1 1

4 2 1 1 5

Note

在第一个示例中，$[3, 1, 2, 4]$ 只有一个有效的顺序，因此每位患者的最小位置等于他们在该顺序中的位置。

在第二个示例中，任何顺序都是有效的，因此任何患者都可以被优先预约。

在第三个示例中，有三个有效的顺序：$[4, 2, 3, 1, 5]$、$[3, 4, 2, 1, 5]$ 和 $[4, 3, 2, 1, 5]$。