#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int T,n,q,v[SZ],rs[SZ]; Edg
#define SS 4209999
int sz[SS],ch[SS][2],an=0;
int ins(int x,int l,int r,int p)
{
int y=++an; sz[y]=sz[x]+1;
if(l==r) return y;
int m=(l+r)>>1;
if(p<=m)
ch[y][1]=ch[x][1],
ch[y][0]=ins(ch[x][0],l,m,p);
else
ch[y][0]=ch[x][0],
ch[y][1]=ins(ch[x][1],m+1,r,p);
return y;
}
int d1[SZ],rv[SZ],ls[SZ],C=0;
void dfs(int x,int f=0)
{
d1[x]=++C; rv[C]=x;
for esb(x,e,b) if(b!=f)
dfs(b,x);
ls[x]=C;
}
int qry(int r1,int r2,int s,int g)
{
if(s<0)
return 0;
int w=(g>>s)&1;
if(ch[r2][!w]!=ch[r1][!w])
return qry(ch[r1][!w],ch[r2][!w],s-1,g)^(1<<s);
return qry(ch[r1][w],ch[r2][w],s-1,g);
}
struct RMQ
{
vector<int> a1,a2,mi; int*A1;
int S=0;
int M;
void pb(pii x)
{
if(!a1.size()) a1.pb(0);
if(!a2.size()) a2.pb(0);
++S; a1.pb(x.fi); a2.pb(x.se);
}
void build()
{
if(M||(!S)) return;
M=1; while(M<S+2) M<<=1;
mi.resize(M+M+1);
if(!is_sorted(&a1[1],&a1[S])) throw "GG";
for(int i=0;i<=M+M;++i) mi[i]=2e9;
for(int i=1;i<=S;++i) mi[i+M]=a2[i];
for(int i=M-1;i>=1;--i)
mi[i]=min(mi[i+i],mi[i+i+1]);
A1=&a1[0];
}
void clr()
{
M=S=0; a1.clear(); a2.clear(); mi.clear();
}
int qmin(int l,int r)
{
int L=lower_bound(A1+1,A1+S,l)-A1,
R=lower_bound(A1+1,A1+1+S,r+1)-A1-1,
ans=2e9;
if(L>R) throw "GG";
l=L; r=R;
for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1) ans=min(ans,mi[l^1]);
if(r&1) ans=min(ans,mi[r^1]);
}
return ans;
}
}sb[1<<20];
namespace FF{
char ch,B[1<<20],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int aa,bb;int F(){
while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
}
}
#define gi FF::F()
#define BUFSIZE 5000000
namespace fob {char b[BUFSIZE]={},*f=b,*g=b+BUFSIZE-2;}
#define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
#define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
struct foce {~foce() {pob; fflush(stdout);}} _foce;
namespace ib {char b[100];}
inline void pint(int x)
{
if(x==0) {pc(48); return;}
if(x<0) {pc('-'); x=-x;}
char *s=ib::b;
while(x) *(++s)=x%10, x/=10;
while(s!=ib::b) pc((*(s--))+48);
}
void sol()
{
n=gi,q=gi; M=C=an=0;
for(int i=1;i<=n;++i)
fst[i]=0,v[i]=gi;
for(int i=1,a,b;i<n;++i) adde(a=gi,b=gi);
dfs(1);
for(int i=1;i<=n;++i)
sb[v[rv[i]]].pb(pii(i,rv[i]));
for(int i=1;i<=n;++i)
sb[v[rv[i]]].build();
for(int i=1;i<=n;++i)
rs[i]=ins(rs[i-1],0,(1<<20)-1,v[rv[i]]);
int la=0,ln=0;
for(int i=0;i<q;++i)
{
int vv=gi,k=gi;
vv^=ln; k^=la;
int L=d1[vv],R=ls[vv];
int w=qry(rs[L-1],rs[R],19,k);
la=w; ln=sb[w^k].qmin(L,R);
pint(ln); pc(' ');
pint(la); pc('\n');
}
for(int i=1;i<=n;++i)
sb[v[i]].clr();
}
int main()
{
T=gi;
// scanf("%d",&T);
while(T--) sol();
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxzdGFjaz4KI2luY2x1ZGUgPGlvbWFuaXA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCnR5cGVkZWYgcGFpcjxpbnQsaW50PiBwaWk7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIGRvdWJsZSBsZDsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIGZlIGZpcnN0CiNkZWZpbmUgRk8oeCkge2ZyZW9wZW4oI3giLmluIiwiciIsc3RkaW4pO2ZyZW9wZW4oI3giLm91dCIsInciLHN0ZG91dCk7fQojZGVmaW5lIEVkZyBpbnQgTT0wLGZzdFtTWl0sdmJbU1pdLG54dFtTWl07dm9pZCBhZF9kZShpbnQgYSxpbnQgYil7KytNO254dFtNXT1mc3RbYV07ZnN0W2FdPU07dmJbTV09Yjt9dm9pZCBhZGRlKGludCBhLGludCBiKXthZF9kZShhLGIpO2FkX2RlKGIsYSk7fQojZGVmaW5lIEVkZ2MgaW50IE09MCxmc3RbU1pdLHZiW1NaXSxueHRbU1pdLHZjW1NaXTt2b2lkIGFkX2RlKGludCBhLGludCBiLGludCBjKXsrK007bnh0W01dPWZzdFthXTtmc3RbYV09TTt2YltNXT1iO3ZjW01dPWM7fXZvaWQgYWRkZShpbnQgYSxpbnQgYixpbnQgYyl7YWRfZGUoYSxiLGMpO2FkX2RlKGIsYSxjKTt9CiNkZWZpbmUgZXMoeCxlKSAoaW50IGU9ZnN0W3hdO2U7ZT1ueHRbZV0pCiNkZWZpbmUgZXNiKHgsZSxiKSAoaW50IGU9ZnN0W3hdLGI9dmJbZV07ZTtlPW54dFtlXSxiPXZiW2VdKQojZGVmaW5lIFNaIDY2NjY2NgppbnQgVCxuLHEsdltTWl0scnNbU1pdOyBFZGcKI2RlZmluZSBTUyA0MjA5OTk5CmludCBzeltTU10sY2hbU1NdWzJdLGFuPTA7CmludCBpbnMoaW50IHgsaW50IGwsaW50IHIsaW50IHApCnsKCWludCB5PSsrYW47IHN6W3ldPXN6W3hdKzE7CglpZihsPT1yKSByZXR1cm4geTsKCWludCBtPShsK3IpPj4xOwoJaWYocDw9bSkKCQljaFt5XVsxXT1jaFt4XVsxXSwKCQljaFt5XVswXT1pbnMoY2hbeF1bMF0sbCxtLHApOwoJZWxzZQoJCWNoW3ldWzBdPWNoW3hdWzBdLAoJCWNoW3ldWzFdPWlucyhjaFt4XVsxXSxtKzEscixwKTsKCXJldHVybiB5Owp9CmludCBkMVtTWl0scnZbU1pdLGxzW1NaXSxDPTA7CnZvaWQgZGZzKGludCB4LGludCBmPTApCnsKCWQxW3hdPSsrQzsgcnZbQ109eDsKCWZvciBlc2IoeCxlLGIpIGlmKGIhPWYpCgkJZGZzKGIseCk7Cglsc1t4XT1DOwp9CmludCBxcnkoaW50IHIxLGludCByMixpbnQgcyxpbnQgZykKewoJaWYoczwwKQoJCXJldHVybiAwOwoJaW50IHc9KGc+PnMpJjE7CglpZihjaFtyMl1bIXddIT1jaFtyMV1bIXddKQoJCXJldHVybiBxcnkoY2hbcjFdWyF3XSxjaFtyMl1bIXddLHMtMSxnKV4oMTw8cyk7CglyZXR1cm4gcXJ5KGNoW3IxXVt3XSxjaFtyMl1bd10scy0xLGcpOwp9CnN0cnVjdCBSTVEKewp2ZWN0b3I8aW50PiBhMSxhMixtaTsgaW50KkExOwppbnQgUz0wOwppbnQgTTsKdm9pZCBwYihwaWkgeCkKewoJaWYoIWExLnNpemUoKSkgYTEucGIoMCk7CglpZighYTIuc2l6ZSgpKSBhMi5wYigwKTsKCSsrUzsgYTEucGIoeC5maSk7IGEyLnBiKHguc2UpOwp9CnZvaWQgYnVpbGQoKQp7CglpZihNfHwoIVMpKSByZXR1cm47CglNPTE7IHdoaWxlKE08UysyKSBNPDw9MTsKCW1pLnJlc2l6ZShNK00rMSk7CglpZighaXNfc29ydGVkKCZhMVsxXSwmYTFbU10pKSB0aHJvdyAiR0ciOwoJZm9yKGludCBpPTA7aTw9TStNOysraSkgbWlbaV09MmU5OwoJZm9yKGludCBpPTE7aTw9UzsrK2kpIG1pW2krTV09YTJbaV07Cglmb3IoaW50IGk9TS0xO2k+PTE7LS1pKQoJCW1pW2ldPW1pbihtaVtpK2ldLG1pW2kraSsxXSk7CglBMT0mYTFbMF07Cn0Kdm9pZCBjbHIoKQp7CglNPVM9MDsgYTEuY2xlYXIoKTsgYTIuY2xlYXIoKTsgbWkuY2xlYXIoKTsKfQppbnQgcW1pbihpbnQgbCxpbnQgcikKewoJaW50IEw9bG93ZXJfYm91bmQoQTErMSxBMStTLGwpLUExLAoJUj1sb3dlcl9ib3VuZChBMSsxLEExKzErUyxyKzEpLUExLTEsCglhbnM9MmU5OwoJaWYoTD5SKSB0aHJvdyAiR0ciOwoJbD1MOyByPVI7Cglmb3IobCs9TS0xLHIrPU0rMTtsXnJeMTtsPj49MSxyPj49MSkKCXsKCQlpZih+bCYxKSBhbnM9bWluKGFucyxtaVtsXjFdKTsKCQlpZihyJjEpIGFucz1taW4oYW5zLG1pW3JeMV0pOwoJfQoJcmV0dXJuIGFuczsKfQp9c2JbMTw8MjBdOwpuYW1lc3BhY2UgRkZ7CmNoYXIgY2gsQlsxPDwyMF0sKlM9QiwqVD1COwojZGVmaW5lIGdldGMoKSAoUz09VCYmKFQ9KFM9QikrZnJlYWQoQiwxLDE8PDIwLHN0ZGluKSxTPT1UKT8wOipTKyspCiNkZWZpbmUgaXNkKGMpIChjPj0nMCcmJmM8PSc5JykKaW50IGFhLGJiO2ludCBGKCl7CiAgICB3aGlsZShjaD1nZXRjKCksIWlzZChjaCkmJmNoIT0nLScpO2NoPT0nLSc/YWE9YmI9MDooYWE9Y2gtJzAnLGJiPTEpOwogICAgd2hpbGUoY2g9Z2V0YygpLGlzZChjaCkpYWE9YWEqMTArY2gtJzAnO3JldHVybiBiYj9hYTotYWE7Cn0KfQojZGVmaW5lIGdpIEZGOjpGKCkKI2RlZmluZSBCVUZTSVpFIDUwMDAwMDAKbmFtZXNwYWNlIGZvYiB7Y2hhciBiW0JVRlNJWkVdPXt9LCpmPWIsKmc9YitCVUZTSVpFLTI7fQojZGVmaW5lIHBvYiAoZndyaXRlKGZvYjo6YixzaXplb2YoY2hhciksZm9iOjpmLWZvYjo6YixzdGRvdXQpLGZvYjo6Zj1mb2I6OmIsMCkKI2RlZmluZSBwYyh4KSAoKihmb2I6OmYrKyk9KHgpLChmb2I6OmY9PWZvYjo6Zyk/cG9iOjApCnN0cnVjdCBmb2NlIHt+Zm9jZSgpIHtwb2I7IGZmbHVzaChzdGRvdXQpO319IF9mb2NlOwpuYW1lc3BhY2UgaWIge2NoYXIgYlsxMDBdO30KaW5saW5lIHZvaWQgcGludChpbnQgeCkKewogICAgaWYoeD09MCkge3BjKDQ4KTsgcmV0dXJuO30KICAgIGlmKHg8MCkge3BjKCctJyk7IHg9LXg7fQogICAgY2hhciAqcz1pYjo6YjsKICAgIHdoaWxlKHgpICooKytzKT14JTEwLCB4Lz0xMDsKICAgIHdoaWxlKHMhPWliOjpiKSBwYygoKihzLS0pKSs0OCk7Cn0Kdm9pZCBzb2woKQp7CgluPWdpLHE9Z2k7IE09Qz1hbj0wOwoJZm9yKGludCBpPTE7aTw9bjsrK2kpCgkJZnN0W2ldPTAsdltpXT1naTsKCWZvcihpbnQgaT0xLGEsYjtpPG47KytpKSBhZGRlKGE9Z2ksYj1naSk7CglkZnMoMSk7Cglmb3IoaW50IGk9MTtpPD1uOysraSkKCQlzYlt2W3J2W2ldXV0ucGIocGlpKGkscnZbaV0pKTsKCWZvcihpbnQgaT0xO2k8PW47KytpKQoJCXNiW3ZbcnZbaV1dXS5idWlsZCgpOwoJZm9yKGludCBpPTE7aTw9bjsrK2kpCgkJcnNbaV09aW5zKHJzW2ktMV0sMCwoMTw8MjApLTEsdltydltpXV0pOwoJaW50IGxhPTAsbG49MDsKCWZvcihpbnQgaT0wO2k8cTsrK2kpCgl7CgkJaW50IHZ2PWdpLGs9Z2k7CgkJdnZePWxuOyBrXj1sYTsKCQlpbnQgTD1kMVt2dl0sUj1sc1t2dl07CgkJaW50IHc9cXJ5KHJzW0wtMV0scnNbUl0sMTksayk7CgkJbGE9dzsgbG49c2Jbd15rXS5xbWluKEwsUik7CgkJcGludChsbik7IHBjKCcgJyk7CgkJcGludChsYSk7IHBjKCdcbicpOwoJfQoJZm9yKGludCBpPTE7aTw9bjsrK2kpCgkJc2JbdltpXV0uY2xyKCk7Cn0KaW50IG1haW4oKQp7CglUPWdpOwovLwlzY2FuZigiJWQiLCZUKTsKCXdoaWxlKFQtLSkgc29sKCk7Cn0=