题目描述

世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小 X 就因为航空管制，连续两次在机场被延误超过了两小时。对此，小 X 表示很不满意。

在这次来烟台的路上，小 X 不幸又一次碰上了航空管制。于是小 X 开始思考关于航空管制的问题。

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

起飞序列还存在两类限制条件：

• 第一类（最晚起飞时间限制）：编号为 $i$ 的航班起飞序号不得超过 $k_i$。
• 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制 $(a,b)$，表示航班 $a$ 的起飞时间必须早于航班 $b$，即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。

小 X 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

输入格式

第一行包含两个正整数 $n$ 和 $m$，$n$ 表示航班数目，$m$ 表示第二类限制条件（相对起飞顺序限制）的数目。

第二行包含 $n$ 个正整数 $k_1,k_2,\cdots,k_n$。

接下来 $m$ 行，每行两个正整数 $a$ 和 $b$，表示一对相对起飞顺序限制 $(a,b)$，其中 $1\leq a,b\leq n$，表示航班 $a$ 必须先于航班 $b$ 起飞。

输出格式

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

第二行包含 $n$ 个整数 $t_1,t_2,\cdots,t_n$，其中 $t_i$ 表示航班 $i$ 可能的最小起飞序号，相邻两个整数用空格分隔。

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

来源

鸣谢 Benz。