#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 2005
#define MAXM 10005
int n, m;
int k[MAXN];
struct Edge
{
    int v, nxt;
} e[MAXM << 1];
int head[MAXN], rhead[MAXN], cnt = 1;
// 建图
void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
    // 顺便存反边，方便后续反图上的DFS
    e[cnt].v = u;
    e[cnt].nxt = rhead[v];
    rhead[v] = cnt++;
}
int vis[MAXN], rvis[MAXN];
int num[MAXN][MAXN], ccnt[MAXN];
// DFS求航班真实k值
int dfs(int cur)
{
    if (vis[cur])
        return k[cur];
    vis[cur] = 1;
    for (int i = head[cur]; i; i = e[i].nxt)
    {
        int res = dfs(e[i].v);
        if (k[cur] > res - 1)
            k[cur] = res - 1;
    }
    // 将航班放到对应k值的航班集合中
    num[k[cur]][ccnt[k[cur]]++] = cur;
    return k[cur];
}
// 反图DFS标记航班及其祖先
void rdfs(int cur)
{
    rvis[cur] = 1;
    for (int i = rhead[cur]; i; i = e[i].nxt)
        if (!rvis[e[i].v])
            rdfs(e[i].v);
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &k[i]);
    while (m--)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v);
    }
    // 求所有航班真实k值
    for (int i = 1; i <= n; i++)
        dfs(i);
    // 按照k值从小到大，从前往后输出所有航班
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < ccnt[i]; j++)
            printf("%d ", num[i][j]);
    printf("\n");
    // 求解每个航班的最早起飞时间
    for (int i = 1; i <= n; i++)
    {
        // 反图DFS标记祖先
        memset(rvis, 0, sizeof(rvis));
        rdfs(i);
        // p为当前所考虑的起飞时间
        int p = n;
        // 按照航班k值从大到小，从后往前安排所有其他航班
        for (int j = n; j >= 1; j--)
        {
            // 从后往前遇到的第一个无法安排其他航班的起飞时间
            // 即为空出来的最后一个起飞时间
            // 此即为所求
            if (p > j)
                break;
            for (int t = 0; t < ccnt[j]; t++)
                if (!rvis[num[j][t]])
                    p--;
        }
        // 输出航班i的最早起飞时间
        printf("%d ", p);
    }
    printf("\n");
    return 0;
}