#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;
constexpr int N = 5e5 + 5;

int n, tp, sz[N], tot, rt, fa[N], v[N];
vector<int> g[N];

struct Buc {
	vector<ll> a;
	int i, j;
	void update() {
		while(i < a.size() && !a[i]) ++ i;
		while(j < a.size() && !a[j]) ++ j;
		if(j < a.size() && i == j && a[j] < 2) ++ j;
		while(j < a.size() && !a[j]) ++ j;
	}
	void add(int p, ll v = 1) {
		if(p >= a.size()) a.resize(p + 1);
		a[p] += v;
	}
	ll cnt() {
		if(j >= a.size()) return 0;
		if(i != j) return a[i] * a[j];
		return a[i] * (a[i] - 1) / 2;
	}
} b[N];

int get_sz(int x, int fa) {
	int sz = 1;
	for(int y : g[x]) {
		if(v[y] || y == fa) continue;
		sz += get_sz(y, x);
	}
	return sz;
}
void get_rt(int x, int fa) {
	int mx = 0; sz[x] = 1; 
	for(int y : g[x]) {
		if(v[y] || y == fa) continue;
		get_rt(y, x);
		mx = max(mx, sz[y]);
		sz[x] += sz[y];
	}
	mx = max(mx, tot - sz[x]);
	if(mx <= tot / 2) rt = x;
}

int d[20][N], dep[N];

void dfs1(int x, int fa) {
	b[rt].add(d[dep[rt]][x]);
	for(int y : g[x]) {
		if(v[y] || y == fa) continue;
		d[dep[rt]][y] = d[dep[rt]][x] + 1;
		dfs1(y, x);
	}
}
void dfs(int x) {
	v[x] = 1;
	dfs1(x, 0);
	b[x].update();
	if(b[x].j < b[x].a.size()) b[0].add(b[x].i + b[x].j, b[x].cnt());
	
	for(int y : g[x]) {
		if(v[y]) continue;
		tot = get_sz(y, 0), get_rt(y, 0);
		fa[rt] = x;
		dep[rt] = dep[x] + 1;
		dfs(rt);
	}
}
void del(int u) {
	int x = u;
	while(1) {
		if(b[x].j < b[x].a.size()) b[0].add(b[x].i + b[x].j, -b[x].cnt());
		b[x].add(d[dep[x]][u], -1);
		b[x].update();
		if(b[x].j < b[x].a.size()) b[0].add(b[x].i + b[x].j, b[x].cnt());
		if(!dep[x]) break;
		x = fa[x];
	}
	b[0].update();
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> tp;
	for(int i = 1, u, v; i <= n - 1; ++ i) {
		cin >> u >> v;
		g[u].eb(v);
		g[v].eb(u);
	}
	tot = n, get_rt(1, 0);
	dfs(rt);
	ll x, lst = 0;
	for(int i = 1; i <= n - 2; ++ i) {
		cin >> x;
		x = x ^ (lst * tp);
		del(x);
		cout << b[0].i << ' ' << (lst = b[0].a[b[0].i]) << '\n';
	}
	return 0;
}