有 $$$n$$$ 人(编号从 $$$1$$$ 到 $$$n$$$)报名了医生预约。医生必须选择任命这些人的顺序。第 $$$i$$$ 患者应被指定为第一批 $$$p_i$$$ 人员。还有以下格式的 $$$m$$$ 限制:第 $$$i$$$ 限制由两个整数 $$$(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$$$ 或两者)。
对输入的附加约束:至少有一个有效的患者订单。
输出
打印 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数等于所有有效订单中第 $$$i$$$ 个患者在订单中的最小位置。订单中的仓位编号从 $$$1$$$ 到 $$$n$$$。
示例
输入 #1
4 1 2 3 2 4 3 1
输出 #1
2 3 1 4
输入 #2
3 0 3 3 3
输出 #2
1 1 1
输入 #3
5 3 4 3 3 2 5 3 1 1 5 4 2
输出 #3
4 2 1 1 5
注意
在第一个示例中,$$$[3, 1, 2, 4]$$$ 是唯一一个有效的顺序,因此每个患者的最小位置等于他们在该顺序中的位置。
在第二个示例中,任何订单都有效,因此可以首先指定任何患者。
在第三个示例中,有三个有效订单:$$$[4, 2, 3, 1, 5]$$$、$$$[3, 4, 2, 1, 5]$$$ 和 $$$[4, 3, 2, 1, 5]$$$。