Air Takeoff Scheduling with Deadlines and Precedence Constraints

During the expo period, the number of airline flights has surged – and with that, air traffic control delays occur frequently. In this problem, you are given n delayed flights, numbered from 1 to n. There is only one runway so that flights must take off one by one according to a takeoff sequence. The takeoff sequence assigns a unique takeoff number (position in the sequence) to every flight.

There are two kinds of restrictions:

• Deadline constraint: For each flight i, its takeoff number must not exceed a given value \(k_i\) (i.e. \(p(i) \le k_i\)).
• Relative order constraint: For some pairs \((a, b)\) a flight a must take off before flight b (i.e. \(p(a) < p(b)\)).

Your task is two‐fold:

1. Determine whether there exists any takeoff sequence which satisfies all constraints.
2. If one exists, for every flight compute the minimum possible takeoff number among all valid takeoff sequences. (Note that the takeoff number is 1-indexed.)
</p>

If no valid sequence exists, output -1.

Note: Any formulas must be written in LaTeX format. In this statement, n is the total number of flights and \(k_i\) is the maximum allowed takeoff position for flight i.

inputFormat

The input begins with a line containing two integers n and m, where n (1 ≤ n ≤ small) is the number of flights and m is the number of relative order restrictions.

The second line contains n integers: k1, k2, ..., kn, where each \(k_i\) (1 ≤ \(k_i\) ≤ n) is the deadline (the maximum allowed takeoff position) for flight i.

Each of the next m lines contains two integers a and b indicating that flight a must take off before flight b (i.e. \(p(a) < p(b)\)).

outputFormat

If there is no valid takeoff sequence satisfying all constraints, output -1.

Otherwise, output n integers on a single line separated by spaces, where the i-th integer is the minimum possible takeoff number (position) of flight i among all valid sequences.

sample

3 1
1 3 3
1 2

1 2 2

</p>