1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include<stdio.h>
#include<string.h>
int head[10200];
int headcnt;
bool win;
struct List {
	int u,v;
	int next;
} edge[20200];
int n,root;
int par[10200];
int ran[10200];
int flag[10200];
int find(int m) {
	if(m==par[m])
		return m;
	else {
		ran[par[m]]++;
		return find(par[m]);
	}
}
void unite(int x,int y) {
	par[y]=x;
}
void dfs(int u) {
	for(int i=head[u]; i!=-1; i=edge[i].next) {
		if(!flag[edge[i].v]&&edge[i].v!=par[u]) {
			unite(u,edge[i].v);
			flag[edge[i].v]=1;
			dfs(edge[i].v);
		}
	}
}
void add(int u,int v) {
	edge[headcnt].u=u;
	edge[headcnt].v=v;
	edge[headcnt].next=head[u];
	head[u]=headcnt++;
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d %d",&n,&root);
		headcnt=0;
		memset(head,-1,sizeof(head));
		memset(flag,0,sizeof(flag));
		for(int i=1; i<=n; i++) {
			par[i]=i;
			ran[i]=0;
		}
		for(int i=1; i<n; i++) {
			int u,v;
			scanf("%d %d",&u,&v);
			add(u,v);
			add(v,u);
		}
		win=true;
		flag[root]=1;
		dfs(root);
		if(win) {
			for(int i=1; i<=n; i++)
				if(find(i)!=root) {
					win=false;
					break;
				}
		}
		if(win) {
			printf("YES\n");
			for(int i=1; i<=n; i++) {
				printf("%d",ran[i]);
				if(i==n)
					printf("\n");
				else
					printf(" ");
			}
			for(int i=1; i<=n; i++) {
				printf("%d",par[i]);
				if(i==n)
					printf("\n");
				else
					printf(" ");
			}
		} else
			printf("NO\n");
	}
	return 0;
}