//#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;
int 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;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en,t,dem1;
int kk;
int el = 19;
int visit(int v);
/*int cdjt[10001];
namespace sample_grader
{
using std::cout;
using std::cin;
using std::endl;
using std::function;
using std::make_pair;
using std::max;
using std::min;
using std::pair;
using std::swap;
using std::vector;
constexpr int tieLimit = 1000000000;
int N;
int dest;
int curr;
vector<int> T;
vector<pair<int, int>> F;
enum { MARK, LOCATE } phase;
[[noreturn]] void die(const char *const s)
{
cout << s << endl;
exit(0);
}
void print_vector(vector<int> v)
{
cout << "{";
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i];
if (i + 1 != v.size()) cout << ", ";
}
cout << "}";
}
void print_vector(vector<pair<int, int>> v)
{
cout << "{";
for (size_t i = 0; i < v.size(); ++i)
{
cout << "{" << v[i].first << ", " << v[i].second << "}";
if (i + 1 != v.size()) cout << ", ";
}
cout << "}";
}
} // namespace sample_grader
int visit(int v)
{
using namespace sample_grader;
function<void()> die_invalid_call_to_visit = [&]()
{
cout << "visit(" << v << ")" << endl;
die("Invalid call to visit");
};
if (phase == MARK || v < 1 || v > N) die_invalid_call_to_visit();
bool adjacent = false;
/* for (auto e : F)
{
if (e == make_pair(v, curr) or e == make_pair(curr, v))
{
adjacent = true;
}
}
if (not adjacent) die_invalid_call_to_visit();
curr = v;
cout << "visit(" << v << ") returned " << T[v - 1] << endl;
return T[cdjt[v] - 1];
}*/
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);
if(n%2==0)
{
s2=-1;
for(auto f:v[x])
if(sz[f]==n/2)
s2=f;
if(s2!=-1)
dfs(s2,x);
}
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];
bool haha[45001];
int heavy[45001];
bool cmd(int x,int y)
{
return sz[x]>sz[y];
}
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;
}
par[s5]=0;
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);
int root=x;
if(n%2==0)
{
s2=-1;
for(auto f:v[x])
if(sz[f]==n/2)
s2=f;
if(s2!=-1)
heavy[x]=0,par[x]=s2;
}
while(true)
{
go[cur]=1;
if(t==0)
{
cur=par[cur];
t=visit(cur);
}
else
{
bool de=0;
s5=0;
for(auto x:v[cur])
if(par[x]==cur&&par[cur]!=x&&!go[x])
s5=max(s5,sz[x]);
for(auto x:v[cur])
if(par[x]==cur&&!go[x]&&par[cur]!=x&&sz[x]==s5)
{
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);
}/*
int main()
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
using namespace sample_grader;
if (!(cin >> N >> dest) or N < 2 or dest < 1 or dest > N) die("Invalid input");
vector<int> deg(N + 1);
for(int i = 1; i < N; ++i)
{
int u, v;
if (!(cin >> u >> v) or min(u, v) < 1 or max(u, v) > N or u == v)
{
die("Invalid input");
}
F.emplace_back(u, v);
++deg[u];
++deg[v];
///if(deg[u] > 3 or deg[v] > 3) die("Invalid input");
}
vector<int> perm;
for(int i=1; i<=N; i++)
perm.pb(i);
random_shuffle(perm.begin(),perm.end());
for(int i=0; i<N; i++)
cdjt[perm[i]]=i+1;
vector<pair<int,int>> FF;
for(auto x:F)
FF.pb({perm[x.first-1],perm[x.second-1]});
vector<bool> visited(N + 1, false);
function<void(int)> visit = [&](int x)
{
visited[x] = true;
for (auto [a, b] : F)
{
if (b == x) swap(a, b);
if (a != x or visited[b]) continue;
visit(b);
}
};
visit(1);
if (not all_of(visited.begin() + 1, visited.end(), [](bool b)
{
return b;
}))
{
die("Invalid input");
}
phase = MARK;
T = mark(F, dest);
cout << "mark(";
print_vector(F);
cout << ", " << dest << ") returned ";
print_vector(T);
cout << endl;
if (T.size() != static_cast<size_t>(N)) die("Invalid return value of mark");
for (int x : T)
{
if (x < 0 or x > tieLimit) die("Invalid return value of mark");
}
phase = LOCATE;
cout << "Enter curr: ";
if (!(cin >> curr) or curr < 1 or curr > N) die("Invalid input");
cout << "locate(";
print_vector(FF);
cout << ", " << curr << ", " << T[cdjt[curr] - 1] << ")" << endl;
locate(FF, curr, T[cdjt[curr] - 1]);
if (curr == perm[dest-1])
{
cout << "Correct: at most " << *max_element(T.begin(), T.end()) << " tie(s) per room" << endl;
}
else
{
assert(0);
cout << "Not correct: current position is " << curr << endl;
}
return 0;
}
*/
