#include<bits/stdc++.h>
using namespace std;
int read() {
//	int o;
//	cin>>o;
//	return o;
	int x=0,f=1;
	char a=getchar();
	while(a<'0'||a>'9') {
		if(a=='-')
			f=-1;
		a=getchar();
	}
	while(a>='0'&&a<='9') {
		x*=10;
		x+=a-'0';
		a=getchar();
	}
	return x*f;
}
int idx=0,h[1000010],next[1000010],z[1000010],fa[500010][21],depth[1000010];
int search(int a,int b) {
//	cout<<a<<b;

	if(depth[a]>depth[b])
		swap(a,b);

	for(int i=20; i>=0; i--) {
//		int o=depth[fa[a][i]];
		if(depth[fa[a][i]]<=depth[b]) {
			a=fa[a][i];
		}
	}
	for(int i=20; i>=0; i--) {
		if(fa[a][i]!=fa[b][i]) {
			a=fa[a][i];
			b=fa[b][i];
		}
	}
//	return 0;
	return a-1;
}
void jian(int root) {
	for(int j=h[root]; j; j=next[j]) {
		fa[j][0]=root;
		depth[j]=depth[root]+1;
		jian(j);
	}
}
void add(int a,int b) {
	idx++;
	next[idx]=h[a];
	h[a]=idx;
	z[idx]=b;
}
int main() {
	int n,m,s,i,j;
	cin>>n>>m>>s;
	for(i=1; i<n; i++) {
		int x,y;
		x=read();
		y=read();
		add(x,y);
	}
	depth[s]=1;
	jian(s);
//	for(i=1;i<=n;i++){
//		for(j=h[i];j;j=next[j]){
//			fa[j][0]=i;
//			depth[j]=depth[i]+1;
//		}
//	}
	for(i=1; i<=n; i++) {
		for(j=0; j<=20; j++) {
			cout<<fa[i][j]<<" ";
		}
		cout<<endl;
	}
	for(i=1; i<=n; i++) {
		for(j=1; j<=20; j++) {
			fa[fa[i][j-1]][j-1]=fa[i][j];
		}
	}

//	for(i=1; i<=m; i++) {
//		int a,b;
//		a=read();
//		b=read();
//		cout<<search(a,b)<<endl;
//	}
	return 0;
}

RT，输出全是零