Problem Description

During the World Expo, Shanghai's air passenger traffic significantly exceeded the usual levels, leading to frequent air traffic control incidents. Recently, Xiao X was delayed at the airport for more than two hours due to air traffic control on two consecutive occasions. Xiao X expressed great dissatisfaction with this.

On his way to Yantai this time, Xiao X unfortunately encountered air traffic control again. This led Xiao X to start thinking about the issues related to 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 need to take off in a certain order (referred to as the takeoff sequence). The takeoff sequence number of a flight is its position in the takeoff sequence, i.e., the order in which it takes off.

The takeoff sequence is subject to two types of constraints:

• Type 1 (Latest Takeoff Time Constraint): The takeoff sequence number of flight $i$ must not exceed $k_i$.

• Type 2 (Relative Takeoff Order Constraint): There are some relative takeoff order constraints $(a, b)$, indicating that flight $a$ must take off before flight $b$, i.e., the takeoff sequence number of flight $a$ must be less than that of flight $b$.

Xiao X's first question is whether, given these two types of constraints, it is possible to calculate a feasible takeoff sequence. The second question is how to determine the minimum takeoff sequence number for each flight considering both types of constraints.

Input Format

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 constraints (relative takeoff order constraints).

The second line contains $n$ positive integers $k_1, k_2, \cdots, k_n$.

The following $m$ lines, each containing two positive integers $a$ and $b$, represent a pair of relative takeoff order constraints $(a, b)$, where $1 \leq a, b \leq n$, indicating that flight $a$ must take off before flight $b$.

Output Format

The first line contains $n$ integers, representing a feasible takeoff sequence, with adjacent integers separated by spaces. The input data guarantees that at least one feasible takeoff sequence exists. If there are multiple feasible solutions, output any one of them.

The second line contains $n$ integers $t_1, t_2, \cdots, t_n$, where $t_i$ represents the possible minimum takeoff sequence number for flight $i$, with adjacent integers separated by spaces.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3 5 1 4 2
3 4 1 2 1

Input Sample #2

5 0
3 3 3 5 5

Output Sample #2

3 2 1 5 4
1 1 1 4 4

Notes

Sample Explanation

In Sample 1:

The takeoff sequence $3\ 5\ 1\ 4\ 2$ meets all the constraints. Other valid takeoff sequences include:

$$ \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} $$

Due to the constraints $(5, 1)$ and $(3, 1)$, flight $1$ can only be scheduled after flights $5$ and $3$, hence the earliest takeoff time is $3$. Other flights follow similarly.

In Sample 2:

Although flights $4$ and $5$ have no relative takeoff order constraints, since flights $1, 2, 3$ must all take off within the first three positions, flights $4$ and $5$ can only take off from the fourth position onwards.

Data Range

For $30\%$ of the data: $n \leq 10$.

For $60\%$ of the data: $n \leq 500$.

For $100\%$ of the data: $n \leq 2 \times 10^3, m \leq 10^4$.

Thanks to @FlierKing for providing the spj.

见题面 Input 部分

见题面 Output 部分