#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_pairvoid 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{	Node *p, *ch[2];	bool rev;	int val;	int mx[2], num[2];	int add, cov;	int size;	bool isRoot;	Node *fa;	Node(){		val = 0; rev = 0;		add = 0; cov = INP;		mx[0] = mx[1] = -INF;		num[0] = num[1] = 0;		size = 0;	}	void setc(Node *c, int d){		ch[d] = c;		c->p = this;	}	bool d(){		return p->ch[1] == this;	}	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]);	}	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;	}	void relax();	void setRoot(Node *f);}Tnull, *null = &Tnull;void Node::setRoot(Node *f){	fa = f;	isRoot = true;	p = null;}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;	}}Node mem[maxn], *C = mem;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++;}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;	}}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();}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 *v[maxn];vector<int> E[maxn];int n, nQ;int que[maxn], fa[maxn], qh = 0, qt = 0;int wht[maxn];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;			}		}	}}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;}void makeRoot(Node *u){	expose(u);	splay(u);	u->revIt();}void addEdge(Node *u, Node *v){	makeRoot(v);	v->fa = u;}void delEdge(Node *u, Node *v){	makeRoot(u);	expose(v); splay(u); u->setc(null, 1); u->upd();	v->setRoot(null);}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]);}Node *find_root(Node *u){	expose(u); splay(u);	while (u->ch[0] != null){		u = u->ch[0];	}	splay(u); return u;}int main(){	int T; cin >> T;int ca=0;	while (T--)	{		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;}