#include <bits/stdc++.h>
using namespace std;
typedef long in;
#define lcm(a,b) ((a*b)/__gcd(a,b))
#define max(a,b) ((a)>(b)?(a):(b))
#define vi vector<in>
#define vvi vector<vector<in> >
#define vpi vector<pair<in,in> >
#define pb push_back
#define mp make_pair
#define pii pair<in,in>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
const in maxn=200005;
vector<in> adj[maxn];
vector<in> val(maxn);
vector<in> ar;
vector<pii> tme(maxn,mp(0,0));
vector<in> flag(maxn);
struct trie
{
trie* arr[2];
in minver,mst;//minimumVertex,maxStartTime
trie() {
arr[0]=arr[1]=NULL;
minver=maxn;
mst=0;
}
};
vector<trie*> ptries(2*maxn);
//persistent trie
trie* insert(trie* root,in ver)
{
trie* newroot=new trie();
trie* source=newroot;
in v=val[ver];
in st=tme[ver].fi;
trie* temp=root;
for(in i=19; i>=0; i--)
{
bool bit=v&(1<<i);
newroot->mst=max(newroot->mst,st);
if(temp!=NULL)
{
newroot->arr[!bit]=temp->arr[!bit];
temp=temp->arr[bit];
}
newroot->arr[bit]=new trie();
newroot=newroot->arr[bit];
}
newroot->mst=max(newroot->mst,st);
newroot->minver=min(newroot->minver,ver);
return source;
}
//euler tour
void dfs(in i,in p)
{
ar.pb(i);
for(in j:adj[i])
if(j!=p)
dfs(j,i);
ar.pb(i);
}
pii querytrie(in ver,in k)
{
trie* root=ptries[tme[ver].se];
in ans=0,v=k;
trie* temp=root;
for(in i=19; i>=0; i--)
{
bool bit=v&(1<<i);
if(temp->arr[!bit]!=NULL && (temp->arr[!bit]->mst)>=tme[ver].fi)//opposite bit there and maxStartTime >=startTime of ver
{
ans=ans|(1<<i);
temp=temp->arr[!bit];
}
else
temp=temp->arr[bit];
}
return {temp->minver,ans};
}
int main() {
// your code goes here
in t;
cin>>t;
while(t--)
{
ar.clear();
ptries.clear();
val.clear();
for(in i=0; i<maxn; i++)
{
adj[i].clear();
tme[i]=mp(0,0);
flag[i]=0;
}
in n,q;
cin>>n>>q;
for(in i=1; i<=n; i++)
cin>>val[i];
for(in i=1; i<n; i++)
{
in a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1,0);
for (int i = 0; i < 2*n; i++) {
if (tme[ar[i]].fi == 0)
tme[ar[i]].fi = i+1;
else
tme[ar[i]].se = i+1;
}
ptries[1]=insert(new trie(),ar[0]);
in j=0;
for(in i=1; i<2*n; i++)
{
if(flag[ar[i]])
{
ptries[i+1]=ptries[i];
}
else
{
flag[ar[i]]=1;
ptries[i+1]=insert(ptries[i],ar[i]);
}
}
in xl=0,vl=0;
for(in i=1; i<=q; i++)
{
in a,b;
cin>>a>>b;
in v=a^vl,k=b^xl;
auto pp=querytrie(v,k);
cout<<pp .fi<<" "<<pp.se<<endl;
xl=pp.se;
vl=pp.fi;
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBpbjsKI2RlZmluZSBsY20oYSxiKSAoKGEqYikvX19nY2QoYSxiKSkKI2RlZmluZSBtYXgoYSxiKSAoKGEpPihiKT8oYSk6KGIpKQojZGVmaW5lIHZpIHZlY3Rvcjxpbj4KI2RlZmluZSB2dmkgdmVjdG9yPHZlY3Rvcjxpbj4gPgojZGVmaW5lIHZwaSB2ZWN0b3I8cGFpcjxpbixpbj4gPgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBpaSBwYWlyPGluLGluPgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIGZpbyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKTsgY291dC50aWUoTlVMTCkKCmNvbnN0IGluIG1heG49MjAwMDA1Owp2ZWN0b3I8aW4+IGFkalttYXhuXTsKdmVjdG9yPGluPiB2YWwobWF4bik7CnZlY3Rvcjxpbj4gYXI7CnZlY3RvcjxwaWk+IHRtZShtYXhuLG1wKDAsMCkpOwp2ZWN0b3I8aW4+IGZsYWcobWF4bik7CnN0cnVjdCB0cmllCnsKICAgIHRyaWUqIGFyclsyXTsKICAgIGluIG1pbnZlcixtc3Q7Ly9taW5pbXVtVmVydGV4LG1heFN0YXJ0VGltZQogICAgdHJpZSgpIHsKICAgICAgICBhcnJbMF09YXJyWzFdPU5VTEw7CiAgICAgICAgbWludmVyPW1heG47CiAgICAgICAgbXN0PTA7CiAgICB9Cn07CnZlY3Rvcjx0cmllKj4gcHRyaWVzKDIqbWF4bik7CgovL3BlcnNpc3RlbnQgdHJpZQp0cmllKiBpbnNlcnQodHJpZSogcm9vdCxpbiB2ZXIpCnsKICAgIHRyaWUqIG5ld3Jvb3Q9bmV3IHRyaWUoKTsKICAgIHRyaWUqIHNvdXJjZT1uZXdyb290OwogICAgaW4gdj12YWxbdmVyXTsKICAgIGluIHN0PXRtZVt2ZXJdLmZpOwogICAgdHJpZSogdGVtcD1yb290OwogICAgZm9yKGluIGk9MTk7IGk+PTA7IGktLSkKICAgIHsKICAgICAgICBib29sIGJpdD12JigxPDxpKTsKICAgICAgICBuZXdyb290LT5tc3Q9bWF4KG5ld3Jvb3QtPm1zdCxzdCk7CiAgICAgICAgaWYodGVtcCE9TlVMTCkKICAgICAgICB7CiAgICAgICAgICAgIG5ld3Jvb3QtPmFyclshYml0XT10ZW1wLT5hcnJbIWJpdF07CiAgICAgICAgICAgIHRlbXA9dGVtcC0+YXJyW2JpdF07CiAgICAgICAgfQogICAgICAgIG5ld3Jvb3QtPmFycltiaXRdPW5ldyB0cmllKCk7CiAgICAgICAgbmV3cm9vdD1uZXdyb290LT5hcnJbYml0XTsKICAgIH0KICAgIG5ld3Jvb3QtPm1zdD1tYXgobmV3cm9vdC0+bXN0LHN0KTsKICAgIG5ld3Jvb3QtPm1pbnZlcj1taW4obmV3cm9vdC0+bWludmVyLHZlcik7CiAgICByZXR1cm4gc291cmNlOwp9Ci8vZXVsZXIgdG91cgp2b2lkIGRmcyhpbiBpLGluIHApCnsKICAgIGFyLnBiKGkpOwogICAgZm9yKGluIGo6YWRqW2ldKQogICAgICAgIGlmKGohPXApCiAgICAgICAgICAgIGRmcyhqLGkpOwogICAgYXIucGIoaSk7Cn0KCnBpaSBxdWVyeXRyaWUoaW4gdmVyLGluIGspCnsKICAgIHRyaWUqIHJvb3Q9cHRyaWVzW3RtZVt2ZXJdLnNlXTsKICAgIGluIGFucz0wLHY9azsKICAgIHRyaWUqIHRlbXA9cm9vdDsKICAgIGZvcihpbiBpPTE5OyBpPj0wOyBpLS0pCiAgICB7CiAgICAgICAgYm9vbCBiaXQ9diYoMTw8aSk7CiAgICAgICAgaWYodGVtcC0+YXJyWyFiaXRdIT1OVUxMICYmICh0ZW1wLT5hcnJbIWJpdF0tPm1zdCk+PXRtZVt2ZXJdLmZpKS8vb3Bwb3NpdGUgYml0IHRoZXJlIGFuZCBtYXhTdGFydFRpbWUgPj1zdGFydFRpbWUgb2YgdmVyCiAgICAgICAgewogICAgICAgICAgICBhbnM9YW5zfCgxPDxpKTsKICAgICAgICAgICAgdGVtcD10ZW1wLT5hcnJbIWJpdF07CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICAgICAgdGVtcD10ZW1wLT5hcnJbYml0XTsKICAgIH0KICAgIHJldHVybiB7dGVtcC0+bWludmVyLGFuc307Cn0KCmludCBtYWluKCkgewogICAgLy8geW91ciBjb2RlIGdvZXMgaGVyZQogICAgaW4gdDsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBhci5jbGVhcigpOwogICAgICAgIHB0cmllcy5jbGVhcigpOwogICAgICAgIHZhbC5jbGVhcigpOwogICAgICAgIGZvcihpbiBpPTA7IGk8bWF4bjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgYWRqW2ldLmNsZWFyKCk7CiAgICAgICAgICAgIHRtZVtpXT1tcCgwLDApOwogICAgICAgICAgICBmbGFnW2ldPTA7CiAgICAgICAgfQogICAgICAgIGluIG4scTsKICAgICAgICBjaW4+Pm4+PnE7CiAgICAgICAgZm9yKGluIGk9MTsgaTw9bjsgaSsrKQogICAgICAgICAgICBjaW4+PnZhbFtpXTsKICAgICAgICBmb3IoaW4gaT0xOyBpPG47IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGluIGEsYjsKICAgICAgICAgICAgY2luPj5hPj5iOwogICAgICAgICAgICBhZGpbYV0ucGIoYik7CiAgICAgICAgICAgIGFkaltiXS5wYihhKTsKICAgICAgICB9CiAgICAgICAgZGZzKDEsMCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyKm47IGkrKykgewogICAgICAgICAgICBpZiAodG1lW2FyW2ldXS5maSA9PSAwKQogICAgICAgICAgICAgICAgdG1lW2FyW2ldXS5maSA9IGkrMTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgdG1lW2FyW2ldXS5zZSA9IGkrMTsKICAgICAgICB9CiAgICAgICAgcHRyaWVzWzFdPWluc2VydChuZXcgdHJpZSgpLGFyWzBdKTsKICAgICAgICBpbiBqPTA7CiAgICAgICAgZm9yKGluIGk9MTsgaTwyKm47IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGlmKGZsYWdbYXJbaV1dKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwdHJpZXNbaSsxXT1wdHJpZXNbaV07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBmbGFnW2FyW2ldXT0xOwogICAgICAgICAgICAgICAgcHRyaWVzW2krMV09aW5zZXJ0KHB0cmllc1tpXSxhcltpXSk7CiAgICAgICAgICAgIH0KCiAgICAgICAgfQogICAgICAgIGluIHhsPTAsdmw9MDsKICAgICAgICBmb3IoaW4gaT0xOyBpPD1xOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBpbiBhLGI7CiAgICAgICAgICAgIGNpbj4+YT4+YjsKICAgICAgICAgICAgaW4gdj1hXnZsLGs9Yl54bDsKICAgICAgICAgICAgYXV0byBwcD1xdWVyeXRyaWUodixrKTsKICAgICAgICAgICAgY291dDw8cHAgLmZpPDwiICI8PHBwLnNlPDxlbmRsOwogICAgICAgICAgICB4bD1wcC5zZTsKICAgICAgICAgICAgdmw9cHAuZmk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIDA7Cn0=