//#include "richest.h"
//#pragma GCC optimize("Ofast,unroll-loops")
#include "incursion.h"
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf=1e18;
const int mod2 = 998244353;
//const int base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en,t,dem1;
ll kk;
ll el = 19;
namespace anna
{
int in[45001];
int sz[45001];
int ou[45001];
vector<int> v[45001];
void dfs(int x,int y)
{
sz[x]=1;
in[x]=++dem;
for(auto f:v[x])
if(f^y)
{
dfs(f,x);
sz[x]+=sz[f];
}
ou[x]=dem;
}
bool check(int x,int y)
{
if(in[x]<=in[y]&&in[y]<=ou[x])return 1;
return 0;
}
int center()
{
dfs(1,0);
s5=1;
for(int i=2; i<=n; i++)
if(sz[i]>n/2)
{
if(sz[i]<sz[s5])
s5=i;
}
return s5;
}
vector<int> mark(vector<pair<int,int>>hihi,int safe)
{
n=hihi.size()+1;
for(auto x:hihi)
v[x.first].pb(x.second),
v[x.second].pb(x.first);
int x=center();
dem=0;
dfs(x,0);
vector<int> send;
for(int i=1; i<=n; i++)
send.pb(check(i,safe));
return send;
}
};
namespace bruno
{
int sz[45001];
int par[45001];
vector<int> v[45001];
bool go[45001];
int heavy[45001];
void dfs(int x,int y)
{
sz[x]=1;
int mxz=0;
heavy[x]=0;
for(auto f:v[x])
if(f^y)
{
par[f]=x;
dfs(f,x);
sz[x]+=sz[f];
if(sz[f]>mxz)
heavy[x]=f;
}
}
int center()
{
dfs(1,0);
s5=1;
for(int i=2; i<=n; i++)
if(sz[i]>n/2)
{
if(sz[i]<sz[s5])
s5=i;
}
return s5;
}
void locate(vector<pair<int,int>>hihi,int cur,int t)
{
n=hihi.size()+1;
for(auto x:hihi)
v[x.first].pb(x.second),
v[x.second].pb(x.first);
int x=center();
dfs(x,0);
while(true)
{
go[cur]=1;
if(t==0)
{
cur=par[cur];
t=visit(cur);
}
else
{
bool de=0;
if(!go[heavy[cur]]&&heavy[cur]!=0)
{
de=1;
cur=heavy[cur];
t=visit(cur);
}
else
{
for(auto x:v[cur])
if(par[x]==cur&&!go[x])
{
cur=x;
t=visit(cur);
de=1;
break;
}
}
if(!de) break;
}
}
}
};
vector<int> mark(vector<pair<int,int>>nmt,int safe)
{
return anna::mark(nmt,safe);
}
void locate(vector<pair<int,int>>nmt,int cur,int t)
{
bruno::locate(nmt,cur,t);
}
/*
void phongbeo()
{
vector<pair<int,int>>haha;
haha.pb({1,2});
haha.pb({2,3});
can[1][2]=1;
can[2][1]=1;
can[2][3]=1;
can[3][2]=1;
vector<int> kiki=anna::mark(haha,1);
for(int i=0;i<kiki.size();i++)
color[i+1]=kiki[i];
root=3;
bruno::locate(haha,3,color[3]);;
cout<<root;
}*/
