#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <vector>#include <algorithm>#include <map>using namespace std; #define ll long long#define maxn 200000#define INF 0x3f3f3f3f#define INP INF+1#define MP make_pair void merge(int mxx[2], int nxx[2], int pval, int pnum){    if (pval>mxx[0]){        mxx[1] = mxx[0]; nxx[1] = nxx[0];        mxx[0] = pval; nxx[0] = pnum;    }    else if (pval == mxx[0]){        nxx[0] += pnum;    }    else if (pval>mxx[1]){        mxx[1] = pval; nxx[1] = pnum;    }    else if(pval==mxx[1]){        nxx[1] += pnum;    }}  struct Node{    /* Splay items(need not to be modified)*/    Node *p, *ch[2];    /* end */    /* LCT items(need not to be modified)*/    bool isRoot;    Node *fa;    /* end */    /* tags to add(rev should always exist)*/    bool rev;    int add, cov;    /* end */    /* data need to be maintained*/    int val, size;    int mx[2], num[2];    /* end */    /* default value for the sentinel null(all the TAG and DATA should be set correcly)*/    Node(){        val = 0; rev = 0;        add = 0; cov = INP;        mx[0] = mx[1] = -INF;        num[0] = num[1] = 0;        size = 0;    }    /* end */    /* LCT function(need not to be modified)*/    void setc(Node *c, int d){        ch[d] = c;        c->p = this;    }    bool d(){        return p->ch[1] == this;    }    /* end */    /* update function(maintain for ALL the DATA)*/    void upd(){        size = ch[0]->size + ch[1]->size + 1;        mx[0] = ch[0]->mx[0]; num[0] = ch[0]->num[0];        mx[1] = ch[0]->mx[1]; num[1] = ch[0]->num[1];        merge(mx, num, val, 1);        merge(mx, num, ch[1]->mx[0], ch[1]->num[0]);        merge(mx, num, ch[1]->mx[1], ch[1]->num[1]);    }    /* end */    /* tags function(for ALL the TAG,write a function)*/    void revIt(){        rev ^= 1;        swap(ch[0], ch[1]);    }    void addIt(int vx){        add += vx;        val += vx;        if (mx[0] != -INF) mx[0] += vx;        if (mx[1] != -INF) mx[1] += vx;    }    void setIt(int vx){        add = 0;        cov = vx;        val = vx;        mx[0] = vx; num[0] = size;        mx[1] = -INF; num[1] = 0;    }    /* end */    void relax();    void setRoot(Node *f);}Tnull, *null = &Tnull;/* function setRoot(need not to be modified) */void Node::setRoot(Node *f){    fa = f;    isRoot = true;    p = null;}/* function relax(need to be set for ALL the TAG) */void Node::relax(){    if (cov != INP){        for (int i = 0; i<2; ++i){            if (ch[i] != null) ch[i]->setIt(cov);        }        cov = INP;    }    if (add != 0){        for (int i = 0; i < 2; i++){            if (ch[i] != null) ch[i]->addIt(add);        }        add = 0;    }    if (rev){        for (int i = 0; i < 2; i++){            if (ch[i] != null) ch[i]->revIt();        }        rev = 0;    }}/* memory part(add C=mem for every iteration)*/Node mem[maxn], *C = mem; /* function make(need to set the default value for ALL the TAG and DATA)*/Node *make(int v){    C->size=1;    C->val = v;    C->rev = 0; C->add = 0;    C->cov = INP;    C->mx[0] = v; C->num[0] = 1;    C->mx[1] = -INF; C->num[1] = 0;    C->ch[0] = C->ch[1] = null; C->isRoot = true;    C->p = null;    C->fa = null;    return C++;} /* function rot(need not to be modified) */void rot(Node *t){    Node *p = t->p;    p->relax();    t->relax();    bool d = t->d();    p->p->setc(t, p->d());    p->setc(t->ch[!d], d);    t->setc(p, !d);    p->upd();    if (p->isRoot){        p->isRoot = false;        t->isRoot = true;        t->fa = p->fa;    }} /* function pushTo(need not to be modified) */void pushTo(Node*t) {    static Node*stk[maxn]; int top = 0;    while (t != null) {        stk[top++] = t;        t = t->p;    }    for (int i = top - 1; i >= 0; --i) stk[i]->relax();}/* function splay(need not to be modified) */void splay(Node*u, Node*f = null) {    pushTo(u);    while (u->p != f) {        if (u->p->p == f)            rot(u);        else            u->d() == u->p->d() ? (rot(u->p), rot(u)) : (rot(u), rot(u));    }    u->upd();}/* Node pointer array*/Node *v[maxn];/* The graph stored in the E*/vector<int> E[maxn];int n, nQ; /* BFS items, using for construct the Tree */int que[maxn], fa[maxn], qh = 0, qt = 0;int wht[maxn]; /* function BFS(need not to be modified) */void bfs(){    qh = qt = 0;    que[qt++] = 1;    fa[1] = -1;    while (qh < qt){        int u = que[qh++];        for (int i = 0; i < E[u].size(); i++){            int e = E[u][i];            if (e != fa[u]){                fa[e] = u;                v[e]->fa = v[u];                que[qt++] = e;            }        }    }} /* function expose(need not to be modified) */Node *expose(Node *u){    Node *v;    for (v = null; u != null; v = u, u = u->fa){        splay(u);        u->ch[1]->setRoot(u);        u->setc(v, 1);        v->fa = u;    }    return v;}/* function makeRoot(need not to be modified) */void makeRoot(Node *u){    expose(u);    splay(u);    u->revIt();}/* function addEdge(need not to be modified) */void addEdge(Node *u, Node *v){    makeRoot(v);    v->fa = u;}/* function delEdge(need not to be modified) */void delEdge(Node *u, Node *v){    makeRoot(u);    expose(v); splay(u); u->setc(null, 1); u->upd();    v->setRoot(null);}/* function find root(need not to be modified) */Node *find_root(Node *u){    expose(u); splay(u);    while (u->ch[0] != null){        u = u->ch[0];    }    splay(u); return u;}/* function used for query*//***************************prototype:void xPath(Node *u,Node *v,(int ax)){    makeRoot(u);    expose(v);    splay(v);    v->xIt((ax))}***************************/void addPath(Node *u, Node *v, int ax){    makeRoot(u);    expose(v);    splay(v);    v->addIt(ax);} void setPath(Node *u, Node *v, int ax){    makeRoot(u);    expose(v);    splay(v);    v->setIt(ax);} pair<int, int> queryPath(Node *u, Node *v){    makeRoot(u);    expose(v);    splay(v);    return MP(v->mx[1], v->num[1]);} int main(){    int T; cin >> T;int ca=0;    while (T--)    {        /*      Things to do     */        /*************************        C=mem;        initialize E;        read in the wht for nodes;        make for each node;        bfs();        solve for query();        **************************/        C = mem;        scanf("%d%d", &n, &nQ);        for (int i = 1; i <= n; i++){            scanf("%d", wht + i);            v[i] = make(wht[i]);        }        for (int i = 0; i <= n; i++) E[i].clear();        int ui, vi;        for (int i = 0; i < n - 1; i++){            scanf("%d%d", &ui, &vi);            E[ui].push_back(vi); E[vi].push_back(ui);        }        bfs();        int cmd, xi, yi, ai, bi;        Node *nx, *ny, *na, *nb;        printf("Case #%d:\n",++ca);        while (nQ--){            scanf("%d", &cmd);            if (cmd == 1) scanf("%d%d%d%d", &xi, &yi, &ai, &bi);            else if (cmd == 2 || cmd == 3) scanf("%d%d%d", &ai, &bi, &xi);            else scanf("%d%d", &ai, &bi);             if (cmd == 1){                nx = v[xi]; ny = v[yi];                na = v[ai]; nb = v[bi];                delEdge(nx, ny);                addEdge(na, nb);            }            else if (cmd == 2){                nx = v[ai]; ny = v[bi];                setPath(nx, ny, xi);            }            else if (cmd == 3){                nx = v[ai]; ny = v[bi];                addPath(nx, ny, xi);            }            else{                nx = v[ai]; ny = v[bi];                pair<int, int> ans = queryPath(nx, ny);                if (ans.first <= -INF) printf("ALL SAME\n");                else printf("%d %d\n", ans.first, ans.second);            }        }    }    return 0;}