世博期间，上海的航空客运量大大超过了平时，随之而来的航空管制也频频发生。最近，小 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
在样例 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。
NOI