National Olympiad in Informatics, China, 2010

Day 2, Problem 1 - Flight Control

During Expo 2010, the number of airline passengers to Shanghai skyrocketed. Due to this, air traffic control systems are also much busier. Recently, little X has been delayed for over two hours at the airport, all because of flight control. Little X is obviously very unsatisfied by this experience.

This time as he is coming to Yantai, little X unfortunately encountered flight control delays once again. That started to make him think about the problem of flight control itself.

Assume that there are n flights that are currently delayed, numbered from 1 to n. The airport only has a single takeoff runway, so all of the flights will follow some particular order for takeoff (call this order the takeoff sequence). Define a flight's takeoff number as its position in the takeoff sequence.

There also two types of restrictions for possible takeoff sequences:

• Type 1 (latest possible takeoff deadline): Flight i cannot have a takeoff number that exceeds k_i.
• Type 2 (relative takeoff order limitation): There exists some restrictions in the form of (a, b) specifying that flight a must take off before flight b (i.e. the takeoff number of flight a must be smaller than the takeoff number of flight b).

The first problem that little X ponders is how to find a valid takeoff sequence when given all of the restrictions. The second problem is, taking the restrictions into account and considering each flight independently, what is the minimum possible takeoff number for each flight out of all the valid takeoff sequences?

Input Format

The first line of input contains two positive integers n and m, respectively representing the number of flights and the number of type 2 constraints.
The second line will contain n integers k₁, k₂, …, k_n, representing the type 1 restrictions.
For the following m lines, each line contains a pair of integers a and b describing a type 2 restriction that flight a must takeoff before flight b.

Output Format

The first line should contain n integers, representing one possible valid takeoff sequence. Adjacent numbers should be separated by a single space. The input will guarantee that there is at least one possible valid takeoff sequence. If there is more than one solution, you may output any one of them.
The second line should contain n integers t₁, t₂, …, t_n, where t_i represents the smallest possible takeoff number of flight i amongst all of the valid solutions. Adjacent numbers should be separated by a single space.

Sample Input 1

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

Sample Output 1

3 5 1 4 2
3 4 1 2 1

Explanation for Sample 1

The flight sequence 3 5 1 4 2 satisfies all of the restrictions. All of the valid takeoff sequences are:

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

Since the restrictions (5, 1) and (3, 1) exist, flight 1's takeoff must be scheduled after the takeoffs of flights 5 and 3, making 3 the earliest possible takeoff number for flight 1. The explanation for other flights are analogous.

Sample Input 2

5 0
3 3 3 5 5

Sample Output 2

3 2 1 5 4
1 1 1 4 4

Explanation for Sample 2

Since flights 4 and 5 do not have any relative takeoff order restrictions and flights 1, 2, and 3 must be scheduled as the first 3 flights, then the earliest time either flight 4 or 5 can takeoff must be 4.

Constraints

For 30% of test cases, n ≤ 10.
For 60% of test cases, n ≤ 500.
For 100% of test cases, n ≤ 2,000 and m ≤ 10,000.

Scoring

If your output is incorrectly formatted or does not fit the requirements of the problem, then you will be given a score of 0. Your output must have exactly n integers on each of the two lines. Satisfying this, then you will be scored as follows:

1. If only the first line is correct, then you will be given 40% of points for the test case.
2. If only the second line is correct, then you will be given 60% of points for the test case.
3. If both lines are correct, then you will be given 100% of points for the test case.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 512M
Added: Aug 08, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)