CF1765H.Hospital Queue

There are $n$ people (numbered from $1$ to $n$) signed up for a doctor's appointment. The doctor has to choose in which order he will appoint these people. The $i$-th patient should be appointed among the first $p_i$ people. There are also $m$ restrictions of the following format: the $i$-th restriction is denoted by two integers $(a_i, b_i)$ and means that the patient with the index $a_i$ should be appointed earlier than the patient with the index $b_i$.

For example, if $n = 4$, $p = [2, 3, 2, 4]$, $m = 1$, $a = [3]$ and $b = [1]$, then the only order of appointment of patients that does not violate the restrictions is $[3, 1, 2, 4]$. For $n =3$, $p = [3, 3, 3]$, $m = 0$, $a = []$ and $b = []$, any order of appointment is valid.

For each patient, calculate the minimum position in the order that they can have among all possible orderings that don't violate the restrictions.

有 $n$ 个人（编号从 $1$ 到 $n$）预约了医生的就诊。医生需要确定这些人就诊的顺序。第 $i$ 位患者必须安排在前 $p_i$ 个就诊者之中。此外还有 $m$ 条限制，每条限制的格式为两个整数 $(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 = []$，则任意就诊顺序均合法。

对每位患者，请计算其在所有不违反限制的就诊顺序中可能占据的最小位置（即最靠前的位置）。

The first line contains two integers $n$ and $m$ ($1 \le n \le 2000$; $0 \le m \le 2000$).

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$).

Then $m$ lines follow. The $i$-th of them contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$; $a_i \ne b_i$). All pairs of $(a_i, b_i)$ are distinct (i. e. if $i \ne j$, then either $a_i \ne a_j$, $b_i \ne b_j$, or both).

Additional constraint on the input: there is at least one valid order of patients.

第一行包含两个整数 $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$ 或两者同时成立）。

输入的附加约束：至少存在一种合法的患者就诊顺序。

Print $n$ integers, where $i$-th integer is equal to the minimum position of $i$-th patient in the order, among all valid orders. Positions in the order are numbered from $1$ to $n$.

输出 $n$ 个整数，其中第 $i$ 个整数等于在所有合法顺序中，第 $i$ 位患者所在位置的最小值。顺序中的位置编号从 $1$ 到 $n$。

In the first example, $[3, 1, 2, 4]$ the only one valid order, so the minimum position of each patient is equal to their position in this order.

In the second example, any order is valid, so any patient can be appointed first.

In the third example, there are three valid orders: $[4, 2, 3, 1, 5]$, $[3, 4, 2, 1, 5]$ and $[4, 3, 2, 1, 5]$.

在第一个例子中，$[3, 1, 2, 4]$ 是唯一有效的顺序，因此每位患者的最小位置即为该顺序中对应的位置。

在第二个例子中，任意顺序均有效，因此任何患者均可被安排在第一位。

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