#include <bits/stdc++.h>
using namespace std;
#include "incursion.h"
vector<int> mark(vector<pair<int, int>> F, int safe) {
int n=F.size()+1;
vector<vector<int>> adj(n);
for(int i=0; i<n-1; i++) adj[F[i].first-1].push_back(F[i].second-1), adj[F[i].second-1].push_back(F[i].first-1);
vector<int> siz(n, 0), par(n);
function<void(int, int)> dfs=[&](int curr, int prev) {
siz[curr]=1;
for(int next:adj[curr]) if(next!=prev) par[next]=curr, dfs(next, curr), siz[curr]+=siz[next];
};
dfs(0, -1);
int cent1=-1, cent2=-1;
for(int i=0; i<n; i++) {
bool flag=true;
for(int next:adj[i]) if(siz[next]<siz[i] && siz[next]>n/2) flag=false;
if(flag && n-siz[i]<=n/2) {
if(cent1<0) cent1=i;
else cent2=i;
}
}
vector<int> ret(n, 1);
dfs(cent1, -1), par[cent1]=-1;
if(cent2>=0) par[cent2]=-1;
for(int i=safe-1; i>=0; i=par[i]) ret[i]=0;
return ret;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
int n=F.size()+1;
vector<vector<int>> adj(n);
for(int i=0; i<n-1; i++) adj[F[i].first-1].push_back(F[i].second-1), adj[F[i].second-1].push_back(F[i].first-1);
vector<int> siz(n, 0), par(n);
function<void(int, int)> dfs=[&](int curr, int prev) {
siz[curr]=1;
for(int next:adj[curr]) if(next!=prev) par[next]=curr, dfs(next, curr), siz[curr]+=siz[next];
};
dfs(0, -1);
int cent1=-1, cent2=-1;
for(int i=0; i<n; i++) {
bool flag=true;
for(int next:adj[i]) if(siz[next]<siz[i] && siz[next]>n/2) flag=false;
if(flag && n-siz[i]<=n/2) {
if(cent1<0) cent1=i;
else cent2=i;
}
}
dfs(cent1, -1), par[cent1]=cent2;
if(cent2>=0) siz[cent1]-=siz[cent2];
vector<vector<int>> chd(n);
for(int i=0; i<n; i++) {
for(int j:adj[i]) if(j!=par[i]) chd[i].push_back(j);
sort(chd[i].begin(), chd[i].end(), [&](int a, int b) {return siz[a]>siz[b];});
}
int prev=-1; curr--;
while(true) {
if(t) {
t=visit(par[curr]+1), prev=curr, curr=par[curr];
}
else {
bool flag=false;
for(int next:chd[curr]) if(next!=prev) {
t=visit(next+1);
if(!t) {
flag=true, prev=curr, curr=next;
break;
}
else visit(curr+1);
}
if(!flag) break;
}
}
}
