#include <bits/stdc++.h>
#include "incursion.h"
#define f0r(i,n) for(int i = 0;i<n;i++)
#define vi vector<int>
#define pb push_back
using namespace std;
const int mxn = 45005;
int n;
int sts[mxn];
vector<int>adj[mxn];
int dfs(int x, int p){
int cur = 1;
for(auto u : adj[x]){
if(u != p){
cur += dfs(u, x);
}
}
sts[x] = cur;
return cur;
}
int centroid(int x, int p){
for(auto u : adj[x]){
if(u != p && sts[u] > n/2)return centroid(u, x);
}
return x;
}
int sts2[mxn];
vector<int>adj2[mxn];
int dfs2(int x, int p){
int cur = 1;
for(auto u : adj2[x]){
if(u != p){
cur += dfs2(u, x);
}
}
sts2[x] = cur;
return cur;
}
int centroid2(int x, int p){
for(auto u : adj2[x]){
if(u != p && sts2[u] > n/2)return centroid2(u, x);
}
return x;
}
int stsc[mxn];
int dfs3(int x, int p){
int cur = 1;
for(auto u : adj2[x]){
if(u != p){
cur += dfs3(u, x);
}
}
stsc[x] = cur;
return cur;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
safe--;
int two;
n = F.size() + 1;
vector<int>dist(n);
dist[safe] = 0;
vi deg(n, 0);
vi degcnt(4, 0);
f0r(i, n-1){
adj[--F[i].first].push_back(--F[i].second);
adj[F[i].second].push_back(F[i].first);
deg[F[i].first]++;
deg[F[i].second]++;
}
//f0r(i,n)cout<<deg[i]<<' ';
//cout<<'\n';
dfs(0, -1);
//f0r(i,n)cout<<sts[i]<<' ';
//cout<<'\n';
int centroid1 = centroid(0, -1);
vi centroids = {centroid1};
for(auto u : adj[centroid1]){
dfs(u, -1);
int thing = centroid(u, -1);
//cout<<u<<' '<<thing<<'\n';
if(thing != centroid1){
centroids.pb(thing);
break;
}
}
//for(auto u : centroids)cout<<u<<' ';
//cout<<'\n';
if(centroids.size() == 1){
two = centroids[0];
vi col(n,0);
vi par(n);
par[two] = -1;
queue<int>q;
q.push(two);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(u != par[cur]){
par[u] = cur;
q.push(u);
}
}
}
//f0r(i,n)cout<<par[i]<<' ';
//cout<<'\n';
int now = safe;
while(now != -1){
//cout<<now<<'\n';
col[now] = 1;
now = par[now];
}
//cout<<cur<<'\n';
//cout<<par[cur]<<'\n';
//cout<<par[par[par[cur]]]<<'\n';
return col;
}
else{
vi col(n,0);
vi par(n);
par[centroids[0]] = centroids[1];
par[centroids[1]] = centroids[0];
queue<int>q;
q.push(centroids[0]);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(u != par[cur]){
par[u] = cur;
q.push(u);
}
}
}
q.push(centroids[1]);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(u != par[cur]){
par[u] = cur;
q.push(u);
}
}
}
//f0r(i,n)cout<<par[i]<<' ';
//cout<<'\n';
int now = safe;
int cnt = 0;
while(cnt == 0){
//cout<<now<<'\n';
col[now] = 1;
if(now == centroids[0] || now == centroids[1])cnt++;
now = par[now];
}
return col;
}
return {};
/*
f0r(i,n){
if(deg[i] == 2)two = i;
degcnt[deg[i]]++;
}
if(degcnt[3] == 0){
vi col(n, 0);
queue<int>q;
q.push(safe);
vector<bool>vis(n,0);
vis[safe] = 1;
col[safe] = 0;
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(vis[u])continue;
vis[u] = 1;
dist[u] = dist[cur] + 1;
col[u] = (col[cur] + 1) % 3;
q.push(u);
}
}
return col;
}
else{
vi col(n,0);
vi par(n);
par[two] = -1;
queue<int>q;
q.push(two);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj[cur]){
if(u != par[cur]){
par[u] = cur;
q.push(u);
}
}
}
//f0r(i,n)cout<<par[i]<<' ';
//cout<<'\n';
int now = safe;
while(now != -1){
//cout<<now<<'\n';
col[now] = 1;
now = par[now];
}
//cout<<cur<<'\n';
//cout<<par[cur]<<'\n';
//cout<<par[par[par[cur]]]<<'\n';
return col;
}
*/
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
int x;
vector<int>nxt = {2, 0, 1};
n = F.size() + 1;
vi deg(n+1);
vi degcnt(4, 0);
f0r(i, n-1){
adj2[F[i].first].push_back(F[i].second);
adj2[F[i].second].push_back(F[i].first);
deg[F[i].first]++;
deg[F[i].second]++;
}
dfs2(1, -1);
//for(int i = 1; i<=n;i++)cout<<sts2[i]<<' ';
//cout<<'\n';
int centroid1 = centroid2(1, -1);
vi centroids = {centroid1};
for(auto u : adj2[centroid1]){
dfs2(u, -1);
int thing = centroid2(u, -1);
if(thing != centroid1){
centroids.pb(thing);
break;
}
}
//for(auto u : centroids)cout<<u<<' ';
//cout<<'\n';
int two;
/*
for(int i = 1; i<=n; i++){
if(deg[i]==2)two = i;
degcnt[deg[i]]++;
}
*/
if(centroids.size() == 2){
vi par(n+1);
dfs3(centroids[0], centroids[1]);
dfs3(centroids[1], centroids[0]);
par[centroids[0]] = centroids[1];
par[centroids[1]] = centroids[0];
queue<int>q;
q.push(centroids[0]);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj2[cur]){
if(u != par[cur]){
par[u] = cur;
q.push(u);
}
}
}
q.push(centroids[1]);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj2[cur]){
if(u != par[cur]){
par[u] = cur;
q.push(u);
}
}
}
vi vis(n+1, 0);
int cur = curr;
int col = t;
int x;
vis[cur] = 1;
while(col == 0){
cur = par[cur];
vis[cur] = 1;
x = visit(cur);
col = x;
}
bool found = 0;
while(!found){
vector<pair<int,int>>thing;
for(auto u : adj2[cur]){
if(!vis[u] && u != par[cur])thing.push_back({stsc[u], u});
}
sort(thing.rbegin(), thing.rend());
bool ok =0;
for(auto u : thing){
x = visit(u.second);
if(x == 0){
visit(cur);
}
else{
cur = u.second;
vis[cur] = 1;
col = x;
ok = 1;
break;
}
}
if(!ok)return;
}
}
else{
two = centroids[0];
//cout<<two<<'\n';
vi par(n+1);
par[two] = -1;
vi d(n+1, 0);
queue<int>q;
q.push(two);
while(!q.empty()){
int cur = q.front();
q.pop();
for(auto u : adj2[cur]){
if(u != par[cur]){
par[u] = cur;
d[u] = d[cur] + 1;
q.push(u);
}
}
}
//for(int i = 1; i<=n; i++)cout<<d[i]<<' ';
//cout<<'\n';
vector<bool>viss(n+1, 0);
vi sts(n+1, 0);
priority_queue<pair<int,int>>pq;
for(int i=1; i<=n;i++){
if(deg[i] == 1){
pq.push({d[i], i});
sts[i] = 1;
viss[i] = 1;
}
}
while(!pq.empty()){
int cur = pq.top().second;
pq.pop();
//cout<<cur<<'\n';
//if(par[cur] != -1)sts[par[cur]] += sts[cur];
if(par[cur] != -1 && !viss[par[cur]]){
viss[par[cur]] = 1;
for(auto u : adj2[par[cur]]){
if(u != par[par[cur]]){
sts[par[cur]] += sts[u];
}
}
pq.push({d[par[cur]], par[cur]});
}
}
//for(int i = 1; i<=n; i++)cout<<sts[i]<<' ';
//cout<<'\n';
vi vis(n+1, 0);
int cur = curr;
int col = t;
int x;
vis[cur] = 1;
while(col == 0){
cur = par[cur];
vis[cur] = 1;
x = visit(cur);
col = x;
}
bool found = 0;
while(!found){
vector<pair<int,int>>thing;
for(auto u : adj2[cur]){
if(!vis[u] && u != par[cur])thing.push_back({sts[u], u});
}
sort(thing.rbegin(), thing.rend());
bool ok =0;
for(auto u : thing){
x = visit(u.second);
if(x == 0){
visit(cur);
}
else{
cur = u.second;
vis[cur] = 1;
col = x;
ok = 1;
break;
}
}
if(!ok)return;
}
}
}
