#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 45005;
vector<int> adj[MAXN];
int marc[MAXN], pai[MAXN], sub[MAXN],n;
int dfsMarc(int s, int p){
for(int viz : adj[s])
if(viz != p) marc[s] |= dfsMarc(viz,s);
return marc[s];
}
void dfsSub(int s, int p){
sub[s] = 1;
for(int viz : adj[s])
if(viz != p){
dfsSub(viz,s);
sub[s] += sub[viz];
}
}
int achaCentroid(int s, int p){
for(int viz : adj[s])
if(viz != p && sub[viz] > n/2)return achaCentroid(viz,s);
return s;
}
vector<int> mark(vector<pair<int, int>> f, int safe) {
n = sz(f)+1;
for(int i = 1; i <= n; i++){
adj[i].clear();
marc[i] = 0;
sub[i] = 0;
}
for(int i = 0; i < sz(f); i++){
adj[ f[i].fi ].push_back( f[i].sc );
adj[ f[i].sc ].push_back( f[i].fi );
}
dfsSub(safe,0);
int rz = achaCentroid(safe,0);
marc[safe] = 1;
dfsMarc(rz,0);
vector<int> ans(n);
for(int i = 1; i <= n; i++)ans[i-1] = marc[i];
return ans;
}
void enraizar(int s){
sub[s] = 1;
for(int viz : adj[s])
if(viz != pai[s]){
pai[viz] = s;
enraizar(viz);
sub[s] += sub[viz];
}
}
void locate(vector<pair<int, int>> f, int ini, int t) {
n = sz(f)+1;
for(int i = 1; i <= n; i++){
adj[i].clear();
marc[i] = 0;
pai[i] = 0;
sub[i] = 0;
}
for(int i = 0; i < sz(f); i++){
adj[ f[i].fi ].push_back( f[i].sc );
adj[ f[i].sc ].push_back( f[i].fi );
}
dfsSub(1,0);
int rz = achaCentroid(1,0);
enraizar(rz);
marc[ini] = t;
int cur = ini;
while(pai[cur] != 0 && marc[cur] == 0){
marc[ pai[cur] ] = visit( pai[cur] );
cur = pai[cur];
}
if(marc[cur] != 1){
for(int viz : adj[cur])
if(sub[viz] == n/2){cur = viz; break;}
}
while(1){
int nxt = -1;
for(int viz : adj[cur])
if( viz != pai[cur] && (nxt == -1 || sub[nxt] < sub[viz]) ) nxt = viz;
if(nxt == -1)return;
marc[ nxt ] = visit( nxt );
if(marc[nxt] == 1)cur = nxt;
else{
visit(cur);
int nxt2 = -1;
for(int viz : adj[cur])
if(viz != pai[cur] && viz != nxt){nxt2 = viz; break;}
if(nxt2 == -1)return;
marc[nxt2] = visit(nxt2);
if(marc[nxt2] != 1){
visit(cur);
return;
}
cur = nxt2;
}
}
}
