#include <bits/stdc++.h>
#define ll int
#define MAX 100005
using namespace std;
ifstream fin("heavypath.in");
ofstream fout("heavypath.out");
ll vec[MAX], val[MAX], liniarizare[MAX], poz[MAX], lvl[MAX], sz[MAX], nrpath[MAX], tata[MAX], aint[4*MAX];
ll nrpaths, ind, n;
vector<ll>v[MAX], path[MAX];
void buildaint(ll nod, ll st, ll dr) {
    if (st==dr) aint[nod]=val[st];
    else {
        ll mij=(st+dr)/2;
        buildaint(2*nod, st, mij);
        buildaint(2*nod+1, mij+1, dr);
        aint[nod]=max(aint[2*nod], aint[2*nod+1]);
    }
}
void update(ll nod, ll st, ll dr, ll pozitie, ll valoare) {
    if (st==dr) aint[nod]=valoare;
    else {
        ll mij=(st+dr)/2;
        if (pozitie<=mij) update(2*nod, st, mij, pozitie, valoare);
        else update(2*nod+1, mij+1, dr, pozitie, valoare);
        aint[nod]=max(aint[2*nod], aint[2*nod+1]);
    }
}
ll query(ll nod, ll st, ll dr, ll a, ll b) {
    if (a<=st && dr<=b) {
        return aint[nod];
    }
    else {
        ll mij=(st+dr)/2, maxi=0;
        if (a<=mij) maxi=max(maxi, query(2*nod, st, mij, a, b));
        if (mij+1<=b) maxi=max(maxi, query(2*nod+1, mij+1, dr, a, b));
        return maxi;
    }
}
ll descompunere(ll a, ll b) {
    ll maxi=0;
    while (true) {
        if (lvl[a]>lvl[b]) swap(a, b);
        if (nrpath[a]==nrpath[b]) {
            maxi=max(maxi, query(1, 1, n, poz[a], poz[b]));
            return maxi;
        }
        maxi=max(maxi, query(1, 1, n, poz[path[nrpath[b]][0]], poz[b]));
        b=tata[path[nrpath[b]][0]];
    }
    return maxi;
}
void dfs(ll nod, ll level) {
    lvl[nod]=level;
    sz[nod]=1;
    ll maxim=0;
    for (auto x:v[nod]) {
        if (lvl[x]!=0) {tata[nod]=x; continue;}
        dfs(x, level+1);
        if (sz[x]>maxim) {
            nrpath[nod]=nrpath[x];
            maxim=sz[x];
        }
        sz[nod]+=sz[x];
    }
    if (nrpath[nod]==0) nrpath[nod]=++nrpaths;
    path[nrpath[nod]].push_back(nod);
}
void hld() {
    ll i;
    dfs(1, 1);
    for (i=1; i<=nrpaths; i++) {
        reverse(path[i].begin(), path[i].end());
        for (auto j:path[i]) {
            liniarizare[++ind]=j;
            poz[j]=ind;
        }
    }
}
int main()
{
    ll i, j, x, y, m, t;
    fin>>n>>m;
    for (i=1; i<=n; i++) fin>>vec[i];
    for (i=1; i<n; i++) {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    hld();
    for (i=1; i<=n; i++) {
        val[i]=vec[liniarizare[i]];
        cout<<val[i]<<' ';
    }
    cout<<'\n';
    for (i=1; i<=n; i++) cout<<poz[i]<<' ';
    buildaint(1, 1, n);
    tata[1]=1;
    while (m--) {
        fin>>t>>x>>y;
        if (t==0) {
            update(1, 1, n, poz[x], y);
        }
        else {
            fout<<descompunere(x, y)<<'\n';
        }
    }
    return 0;
}