1 #include <set>
2 #include <map>
3 #include <cmath>
4 #include <queue>
5 #include <vector>
6 #include <cstdio>
7 #include <cstdlib>
8 #include <cstring>
9 #include <iostream>
10 #include <algorithm>
11 using namespace std;
12 const int MAXN=100010,MAXM=200010;
13 struct edge{
14 int v,next;
15 edge(int v=0,int next=0):v(v),next(next){}
16 };
17
18 edge E[MAXM];int head[MAXN],cnt,d[MAXN],sg[MAXN],g,rt;
19 void add(int u,int v){E[++cnt]=edge(v,head[u]),head[u]=cnt;}
20
21 void init(){
22 cnt=g=0;
23 memset(d,0,sizeof(d));
24 memset(head,0,sizeof(head));
25 }
26
27 void dfs(int u,int fa){
28 sg[u]=0;
29 for(int i=head[u];i;i=E[i].next)
30 if(E[i].v!=fa)
31 dfs(E[i].v,u);
32 sg[fa]^=(sg[u]+1);
33 if(fa==rt)g^=sg[u];
34 }
35
36 int main(){
37 int q,n;
38 for(scanf("%d",&q);q--;){
39 init(),scanf("%d",&n);
40 for(int i=1,u,v; i<n; i++)scanf("%d%d",&u,&v),add(u,v),d[v]++;
41 for(int i=1;i<=n;i++)if(!d[i])rt=i;//注意题目的隐含意思是加入的单项边
42 dfs(rt,0);
43 putchar(sg[rt]?'1':'0');
44 putchar(g?'1':'0');
45 }
46 return 0;
47 }
