#include <bits/stdc++.h>
using namespace std;

int stramosi[100005];
vector <int> arbore[100005];
bitset <100005> areTata;
int parcurgeri[100005];

deque <int> stramosi2;
void cautaNepoti(int maimuta) {
    for (unsigned int i = 0; i < arbore[maimuta].size(); ++i) {
        int nepot = arbore[maimuta][i];
        stramosi2.push_back(nepot);
        stramosi[nepot] = stramosi2[stramosi2.size() - 1 - stramosi[nepot]];
        cautaNepoti(nepot);
        stramosi2.pop_back();
    }
}

void calculeazaParcurgerile(int maimuta) {
    if (!(stramosi[maimuta] == maimuta))
        parcurgeri[maimuta] = parcurgeri[stramosi[maimuta]] + 1;

    for (unsigned int i = 0; i < arbore[maimuta].size(); ++i)
        calculeazaParcurgerile(arbore[maimuta][i]);
}

int main() {
    ifstream fin("cerere.in");
    ofstream fout("cerere.out");

    int n;
    fin >> n;

    queue <int> posibileRadacini;
    for (int i = 1; i <= n; ++i) {
        fin >> stramosi[i];

        if (stramosi[i] == 0)
            posibileRadacini.push(i);
    }

    for (int i = 1; i < n; ++i) {
        int x, y;
        fin >> x >> y;
        arbore[x].push_back(y);
        areTata[y] = true;
    }

    //Cauta radacina
    int radacina;
    while (!posibileRadacini.empty()) {
        if (!areTata[posibileRadacini.front()]) {
            radacina = posibileRadacini.front();
            break;
        }
        posibileRadacini.pop();
    }
    cout << radacina << "\n";

    stramosi[radacina] = radacina;
    stramosi2.push_back(radacina);
    cautaNepoti(radacina);
    calculeazaParcurgerile(radacina);

    for (int i = 1; i <= n; ++i)
        cout << stramosi[i] << " ";

    for (int i = 1; i <= n; ++i)
        fout << parcurgeri[i] << " ";

    return 0;
}