#include <bits/stdc++.h>
#define NMAX 100005
#define pb push_back

using namespace std;

int v[NMAX], fr[NMAX*10],res[2*NMAX],n,sqrt_;
int LCA[18][NMAX], depth[NMAX];
bool viz[NMAX];
int euler[2*NMAX], nrord;
int in[NMAX], out[NMAX];
vector<int> G[NMAX];


struct query {
    int st, dr, i;
} q[2*NMAX];

void DFS(int node, int level) {
    euler[++nrord] = node;
    LCA[0][nrord] = node;
    in[node] = nrord;

    depth[node] = level;
    viz[node] = 1;

    for(auto it:G[node])
        if(!viz[it])
            DFS(it, level+1);

    euler[++nrord] = node;
    out[node] = nrord;
}

bool mo(query A, query B) {
    if(A.st/sqrt_ == B.st/sqrt_)
        return A.dr < B.dr;
    return A.st/sqrt_ < B.st/sqrt_;
}

void remove(int pos, int &ans) {
    --fr[v[pos]];
    if(fr[v[pos]] == 0) --ans;
}

void insert(int pos, int &ans) {
    ++fr[v[pos]];
    if(fr[v[pos]] == 1) ++ans;
}

int getLCA(int x, int y) {
    if(depth[x] > depth[y]) swap(x,y);


}

int main() {
    int m,i,x,y;

    freopen("fisier.in", "r", stdin);

    cin>>n>>m;
    map<int,int> normalized;
    for(i=1;i<=n;++i) {
        cin >> v[i];

        if(normalized.find(v[i]) == normalized.end())
            normalized[v[i]] = normalized.size();

        v[i] = normalized[v[i]];
    }

    for(i=1;i<n;++i) {
        cin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }

    DFS(1,0);
    for(i=1;i<=n;++i) {
        cout << in[i] << ' ' << out[i] << '\n';
    }

    // LCA
    for(i=1;(1<<i)<=nrord;++i) {
        for(j=1;j+(1<<i)-1<=nrord;++j) {
            if(depth[LCA[i-1][j]] < depth[LCA[i-1][j+(1<<i)]])
                LCA[i][j] = LCA[i-1][j];
            else LCA[i][j] = LCA[i-1][j+(1<<i)];
        }
    }

    // for(i=1;i<=m;++i) {
    //     cin >> q[i].st >> s[i].dr;
    //     q[i].i = i;
    //
    //     getLCA(q[i].st, q[i].dr);
    // }

    return 0;
}