#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n,op,fa[N],siz[N],zd[N],mk[N],bk[N],zx,ans,res,cs[N],dep[25][N],mx,rs[N],r1[N],r2[N],sm[N],sz[N],zs[N],gr[N];
vector<int>p[N],f[N],g[N],dy[N];
void dfs1(int x,int y,int*dep){
    mx=max(mx,dep[x]);
    mk[x]=1;siz[x]=1;zd[x]=0;
    for(auto c:p[x]){
        if(mk[c]||bk[c])continue;
        dep[c]=dep[x]+1;
        dfs1(c,y,dep);
        siz[x]+=siz[c];
        zd[x]=max(zd[x],siz[c]);
    }
    zd[x]=max(zd[x],y-siz[x]);
    if(!zx||zd[x]<zd[zx])zx=x;
    mk[x]=0;
}
void dfs2(int x,vector<int>&f,int*dep){
    f[dep[x]]++;
    mk[x]=1;
    for(auto c:p[x]){
        if(mk[c]||bk[c])continue;
        dfs2(c,f,dep);
    }
    mk[x]=0;
}
void solve(int x){
    bk[x]=1;
    dep[cs[x]][x]=0;mx=0;
    dfs1(x,0,dep[cs[x]]);
    f[x].resize(mx+1);
    sz[x]=mx;
    dy[x].resize(mx+1);
    dy[x].push_back(2);
    dy[x][0]++;
    r1[x]=0;r2[x]=1;
    if(siz[x]==1)return;
    dfs2(x,f[x],dep[cs[x]]);
    sm[1]++;
    for(auto c:p[x]){
        if(bk[c])continue;
        dy[x][1]++;
        zx=0;mx=0;
        dfs1(c,siz[c],dep[cs[x]]);
        g[zx].resize(mx+1);g[zx].push_back(2);
        dfs2(c,g[zx],dep[cs[x]]);
        fa[zx]=x;rs[zx]=1;zs[zx]=mx;
        cs[zx]=cs[x]+1;
        solve(zx);
    }
}
void del(int x,int y,int c=0){
    if(r2[x]<=sz[x])sm[r1[x]+r2[x]]--;
    if(x==y){
        f[x][0]--;dy[x][0]--;
        r1[x]=r2[x];
        if(dy[x][r2[x]]==1){
            r2[x]++;
            while(!dy[x][r2[x]])r2[x]++;
        }
    }else{
        int k=dep[cs[x]][y];
        f[x][k]--;g[c][k]--;
        if(!g[c][rs[c]]){
            if(rs[c]<=zs[c])dy[x][rs[c]]--;
            while(!g[c][rs[c]])rs[c]++;
            if(rs[c]<=zs[c])dy[x][rs[c]]++;
            while(!dy[x][r1[x]])r1[x]++;
            if(r1[x]==r2[x]&&dy[x][r2[x]]<2)r2[x]++;
            while(!dy[x][r2[x]])r2[x]++;
        }
    }
    if(r2[x]<=sz[x])sm[r1[x]+r2[x]]++;
    if(x!=1)del(fa[x],y,x);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    #ifdef zzafanti
    freopen("in.txt","r",stdin);
    #endif
    #ifdef orz
    freopen("out.txt","w",stdout);
    #endif
    cin>>n>>op;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        p[x].push_back(y);
        p[y].push_back(x);
    }
    solve(1);
    for(int i=1;i<=n-2;i++){
        int x;
        cin>>x;
        x^=(res*op);x=i;
        del(x,x);
        while(!sm[ans])ans++;
        cout<<ans<<" "<<res<<"\n";
    }
}