Hospital Queue
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 2200
Tags: binary search, graphs, greedy, implementation

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.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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]$$$.

Example input:
4 1
2 3 2 4
3 1

Example output:
2 3 1 4

Example input:
3 0
3 3 3

Example output:
1 1 1

Editorial:
Let's solve the problem separately for each patient.
Let's assume that we are solving a problem for a patient with the number $$$s$$$. Let's iterate through the positions in the queue from the end, and the current position is $$$i$$$.
Why do we try to construct the queue from the end, and not from its beginning? This allows us to handle the constraint on $$$p_i$$$ for each patient easier. If we try to form the queue starting from the beginning, we have to be very careful with these constraints on $$$p_i$$$, since placing a patient on some position might make it impossible to continue the order, but it's very difficult to understand when it concerns us. On the other hand, if we go from the end to the beginning, each patient that we can place on the current position can be placed on any of the positions we consider later as well, so our actions won't "break" the correct order; any order we build while maintaining all of the constraints for its suffix is correct. That's why this problem is easier to solve if we construct the queue backwards.
Now, all we need to do is try not to place patient $$$s$$$ as long as possible. So, we can maintain all patients we can place (such a patient $$$x$$$ that $$$x$$$ is not placed yet, $$$p_x \ge i$$$ and there is no such patient $$$y$$$, that $$$x$$$ should be in the queue before $$$y$$$, but $$$y$$$ is not placed yet) now in any data structure, and when choosing who to place on each position, we delay placing patient $$$s$$$ as long as possible.