P1954 [NOI2010] 航空管制

世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小 X 就因为航空管制，连续两次在机场被延误超过了两小时。对此，小 X 表示很不满意。 在这次来烟台的路上，小 X 不幸又一次碰上了航空管制。于是小 X 开始思考关于航空管制的问题。 假设目前被延误航班共有 $n$ 个，编号为 $1$ 至 $n$。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。 起飞序列还存在两类限制条件： - 第一类（最晚起飞时间限制）：编号为 $i$ 的航班起飞序号不得超过 $k_i$。 - 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制 $(a,b)$，表示航班 $a$ 的起飞时间必须早于航班 $b$，即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。 小 X 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

无

无

### 样例解释 在样例 $1$ 中： 起飞序列 $3\ 5\ 1\ 4\ 2$ 满足了所有的限制条件，所有满足条件的起飞序列有： $$ \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} $$ 由于存在 $(5,1)$ 和 $(3,1)$ 两个限制，航班 $1$ 只能安排在航班 $5$ 和 $3$ 之后，故最早起飞时间为 $3$，其他航班类似。 在样例 $2$ 中： 虽然航班 $4,5$ 没有相对起飞顺序限制，但是由于航班 $1,2,3$ 都必须安排在前 $3$ 个起飞，所以 $4,5$ 最早只能安排在第 $4$ 个起飞。 ### 数据范围 对于 $30\%$ 数据：$n\leq 10$。 对于 $60\%$ 数据：$n\leq 500$。 对于 $100\%$ 数据：$n\leq 2\times 10^3,m\leq 10^4$。 感谢 @FlierKing 提供 spj