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

const int MAXN = 100000 + 10, inf = 2e9;

struct Node *null;
struct Node {
    Node *p, *ch[2];
    int sz, val, m1, m2, c1, c2;
    int add, same, rev;
    bool d() {return this == p->ch[1];}
    bool isroot() {return p == null || (p->ch[0] != this && p->ch[1] != this);}
    void setc(Node *c, int d) {ch[d] = c; c->p = this;}
    void flip() {swap(ch[0], ch[1]); rev ^= 1;}
    void go() {if (!isroot()) p->go(); pushdown();}
    void rot() {
        Node *f = p, *ff = p->p;
        int c = d(), cc = p->d();
        f->setc(ch[!c], c); this->setc(f, !c);
        if (ff->ch[cc] == f) ff->setc(this, cc);
        else this->p = ff;
        f->update();
    }
    Node* splay() {
        for (go(); !isroot(); rot()) {
            if (!p->isroot()) d() == p->d() ? p->rot() : rot();
        }
        update(); return this;
    }
    Node* access() {
        for (Node *x = this, *y = null; x != null; y = x, x = x->p) {
            x->splay()->setc(y, 1); x->update();
        }
        return splay();
    }
    Node* find_root() {
        Node *x;
        for (x = access(); x->pushdown(), x->ch[0] != null; x = x->ch[0]);
        return x;
    }
    void make_root() {
        access()->flip();
    }
    void cut() {
        access(); ch[0]->p = null; ch[0] = null; update();
    }
    void cut(Node *x) {
        if (this == x || find_root() != x->find_root()) return;
        else {x->make_root(); cut();}
    }
    void link(Node *x) {
        if (find_root() == x->find_root()) return;
        else {make_root(); p = x;}
    }
    // modify according to problem
    void setval(int v = -inf) {
        p = ch[0] = ch[1] = null;
        m1 = val = v; c1 = sz = 1;
        m2 = same = -inf; c2 = add = rev = 0;
    }
    void mark_add(int w) {
        if (this == null) return;
        if (m1 != -inf) m1 += w;
        if (m2 != -inf) m2 += w;
        val += w; add += w;
    }
    void mark_same(int w) {
        if (this == null) return;
        m1 = w, c1 = sz; m2 = -inf, c2 = 0;
        same = w; val = w; add = 0;
    }
    void pushdown() {
        if (same != -inf) {ch[0]->mark_same(same); ch[1]->mark_same(same);}
        if (add) {ch[0]->mark_add(add); ch[1]->mark_add(add);}
        if (rev) {ch[0]->flip(); ch[1]->flip();}
        same = -inf, add = rev = 0;
    }
    void take_best(int _m, int _c) {
        if (_m == -inf || _m < m2) return;
        if (_m == m2) c2 += _c;
        else if (_m < m1) m2 = _m, c2 = _c;
        else if (_m == m1) c1 += _c;
        else m2 = m1, c2 = c1, m1 = _m, c1 = _c;
    }
    void update() {
        sz = 1 + ch[0]->sz + ch[1]->sz;
        m2 = -inf, c2 = 0; m1 = val, c1 = 1;
        take_best(ch[0]->m1, ch[0]->c1); take_best(ch[0]->m2, ch[0]->c2);
        take_best(ch[1]->m1, ch[1]->c1); take_best(ch[1]->m2, ch[1]->c2);
    }
} mem[MAXN], *pt[MAXN], *cnt;

int M1, C1, M2, C2;
void take_best(int _m, int _c) {
    if (_m == -inf || _m < M2) return;
    if (_m == M2) C2 += _c;
    else if (_m < M1) M2 = _m, C2 = _c;
    else if (_m == M1) C1 += _c;
    else M2 = M1, C2 = C1, M1 = _m, C1 = _c;
}

void query_max(Node *x, Node *y) {
    for (x->access(), x = null; y != null; x = y, y = y->p) {
        y->splay();
        if (y->p == null) {
            M1 = y->val, C1 = 1; M2 = -inf, C2 = 0;
            take_best(y->ch[1]->m1, y->ch[1]->c1);
            take_best(y->ch[1]->m2, y->ch[1]->c2);
            take_best(x->m1, x->c1);
            take_best(x->m2, x->c2);
            return;
        }
        y->setc(x, 1); y->update();
    }
}

void ADD(Node *x, Node *y, int w) {
    for (x->access(), x = null; y != null; x = y, y = y->p) {
        y->splay();
        if (y->p == null) {
            y->ch[1]->mark_add(w);
            x->mark_add(w);
            y->val += w;
            y->update();
            return;
        }
        y->setc(x, 1); y->update();
    }
}

void SAME(Node *x, Node *y, int w) {
    for (x->access(), x = null; y != null; x = y, y = y->p) {
        y->splay();
        if (y->p == null) {
            y->ch[1]->mark_same(w);
            x->mark_same(w);
            y->val = w;
            y->update();
            return;
        }
        y->setc(x, 1); y->update();
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++ cas) {
        printf("Case #%d:\n", cas);
        int n, m; scanf("%d%d", &n, &m);
        cnt = mem; null = cnt ++;
        null->setval(); null->c1 = null->sz = 0;
        for (int i = 0; i < n; ++ i) {
            int x; scanf("%d", &x);
            pt[i] = cnt ++; pt[i]->setval(x);
        }
        for (int i = 1; i < n; ++ i) {
            int u, v; scanf("%d%d", &u, &v);
            -- u, -- v; pt[u]->link(pt[v]);
        }
        while (m --) {
            int op, a, b, x, y; scanf("%d", &op);
            if (op == 1) {
                scanf("%d%d%d%d", &a, &b, &x, &y);
                -- a; -- b; -- x; -- y;
                pt[a]->cut(pt[b]); pt[x]->link(pt[y]);
            }
            else if (op == 2) {
                scanf("%d%d%d", &a, &b, &x); -- a; -- b;
                SAME(pt[a], pt[b], x);
            }
            else if (op == 3) {
                scanf("%d%d%d", &a, &b, &x); -- a; -- b;
                ADD(pt[a], pt[b], x);
            }
            else {
                scanf("%d%d", &a, &b); -- a, -- b;
                query_max(pt[a], pt[b]);
                if (M2 == -inf) puts("ALL SAME");
                else printf("%d %d\n", M2, C2);
            }
        }
    }
    return 0;
}