航班延误

题目描述

目前机场有$n$趟被延误航班，编号为$1$至$n$。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞时间为该航班在起飞序列中的位置，即是第几个起飞的航班。

起飞序列必须满足以下条件：

• 限制一：编号为$i$的航班起飞时间不得超过$k_{i}$。
• 限制二：存在一些相对起飞顺序限制$(a,b)$，表示航班$a$必须在航班$b$之前起飞。

有两个问题：

1. 在考虑两类限制条件的情况下，是否可以计算出一个可行的起飞序列。
2. 在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞时间。

输入格式

第一行包含两个正整数$n$和$m$，$m$表示限制二的数目。

第二行包含$n$个正整数$k$。

接下来$m$行，每行两个正整数$a$和$b$，表示一对限制二$(a,b)$，其中$1 \leq a,b \leq n$。

输出格式

第一行包含$n$个整数，表示一个可行的起飞序列，相邻两个整数用空格分隔。输入数据保证至少存在一个可行的起飞序列。如果存在多个可行的方案，输出任意一个即可。

第二行包含$n$个整数$t$，其中$t$表示航班$i$可能的最小起飞时间，相邻两个整数用空格分隔。

数据范围与提示

• 对于$30\%$的数据，满足$n \leq 10$；
• 对于$60\%$的数据，满足$n \leq 500$；
• 对于$100\%$的数据，满足$1 \leq n \leq 2 \times 10^{3}$，$0 \leq m \leq 10^{4}$。

样例

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

3 5 1 4 2
3 4 1 2 1

5 0
3 3 3 5 5

3 2 1 5 4
1 1 1 4 4

见airport3.in

见airport3.out