#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=1e5+5;
int f[N],sz[N],n,ID,dep[N];
vector<int>G[N];
void dp(int u,int fa){
	sz[u]=1;
	for(int v:G[u])if(v!=fa)dep[v]=dep[u]+1,dp(v,u),sz[u]+=sz[v];
	int mx=0;
	for(int v:G[u])if(v!=fa){
		if(mx==0||f[mx]<f[v])mx=v;
	}
	if(!mx)return f[u]=0,void();
	int lf=f[mx]+1;
	for(int v:G[u])if(v!=fa&&v!=mx)lf-=sz[v];
	if(lf<0)f[u]=(sz[u]%2==0?1:0);
	else f[u]=lf;
}

set<pair<int,int> >S;
bool ans[N];
int sum=0;
void dfs(int u,int fa){
	for(int v:G[u])if(v!=fa)sum+=sz[v],S.insert(mk(f[v]+1,v));
	if(dep[u]%2==(n-1)%2){
		auto [F,p]=*--S.end();
		if(F>sum-sz[p])ans[u]=0;
		else ans[u]=1;
	}
	for(int v:G[u])if(v!=fa){
		S.erase(mk(f[v]+1,v)),sum-=sz[v];
		dfs(v,u);
		sum+=sz[v],S.insert(mk(f[v]+1,v));
	}
	for(int v:G[u])if(v!=fa)sum-=sz[v],S.erase(mk(f[v]+1,v));
}

void solve(){
	n=read();
	if(n==1){puts("1");return ;}
	for(int i=2;i<=n;i++){
		int u=read(),v=read();
		G[u].emplace_back(v),G[v].emplace_back(u);
	}
	dp(1,0),dfs(1,0);
	if(ID==3)cout<<ans[1]<<endl;
	else{for(int i=1;i<=n;i++)cout<<ans[i];puts("");}

	for(int i=1;i<=n;i++)G[i].clear(),f[i]=sz[i]=ans[i]=0;
	S.clear();
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("5.in","r",stdin);
	freopen("5.out","w",stdout);
#endif

	ID=read();int tt=read();while(tt--)solve();

	return 0;
}