P1954 [NOI2010] Air Traffic Control

During the World Expo, Shanghai’s air passenger traffic greatly exceeded normal levels, and air traffic control also occurred frequently. Recently, Xiao X was delayed at the airport for more than two hours twice in a row due to air traffic control. Xiao X was very dissatisfied with this. On the way to Yantai this time, Xiao X unfortunately encountered air traffic control again. So Xiao X began to think about the problem of air traffic control. Suppose there are currently $n$ delayed flights, numbered from $1$ to $n$. The airport has only one takeoff runway, and all flights must take off one by one in some order (called the takeoff sequence). Define a flight’s takeoff position as its position in the takeoff sequence, i.e., the index of when it takes off. There are two types of constraints on the takeoff sequence: - Type 1 (latest takeoff position limit): the takeoff position of flight $i$ must not exceed $k_i$. - Type 2 (relative takeoff order constraints): there are some constraints $(a,b)$, meaning flight $a$ must take off earlier than flight $b$, i.e., the takeoff position of flight $a$ must be less than that of flight $b$. Xiao X’s first question is: given the two types of constraints above, can we compute a feasible takeoff sequence? The second question is: considering both types of constraints, how to compute for each flight its minimal possible takeoff position among all feasible takeoff sequences.

The first line contains two positive integers $n$ and $m$, where $n$ is the number of flights and $m$ is the number of Type 2 (relative takeoff order) constraints. The second line contains $n$ positive integers $k_1,k_2,\cdots,k_n$. The next $m$ lines each contain two positive integers $a$ and $b$, representing one relative takeoff order constraint $(a,b)$, where $1\leq a,b\leq n$, meaning flight $a$ must take off before flight $b$.

The first line contains $n$ integers representing one feasible takeoff sequence, with adjacent integers separated by single spaces. The input guarantees that at least one feasible takeoff sequence exists. If there are multiple feasible sequences, output any one of them. The second line contains $n$ integers $t_1,t_2,\cdots,t_n$, where $t_i$ is the minimal possible takeoff position of flight $i$ among all feasible sequences, with adjacent integers separated by single spaces.

### Sample Explanation In sample $1$: The takeoff sequence $3\ 5\ 1\ 4\ 2$ satisfies all the constraints. All takeoff sequences that satisfy the constraints are: $$ \begin{aligned} 3\ 4\ 5\ 1\ 2\\ 3\ 5\ 1\ 2\ 4\\ 3\ 5\ 1\ 4\ 2\\ 3\ 5\ 4\ 1\ 2\\ 5\ 3\ 1\ 2\ 4\\ 5\ 3\ 1\ 4\ 2\\ 5\ 3\ 4\ 1\ 2 \end{aligned} $$ Because there are constraints $(5,1)$ and $(3,1)$, flight $1$ can only be scheduled after flights $5$ and $3$, so its earliest takeoff position is $3$. Other flights are similar. In sample $2$: Although flights $4,5$ have no relative takeoff order constraints, since flights $1,2,3$ must occupy the first $3$ takeoff positions, $4,5$ can be scheduled no earlier than position $4$. ### Constraints For $30\%$ testdata: $n\leq 10$. For $60\%$ testdata: $n\leq 500$. For $100\%$ testdata: $n\leq 2\times 10^3,m\leq 10^4$. Thanks to @FlierKing for providing the special judge (SPJ). Translated by ChatGPT 5