#include "incursion.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n;
const int MAXN=45000;
vector<vector<int>> graph;
int sz[MAXN+1],pa[MAXN+1];
bool spe[MAXN+1],insub[MAXN+1];
vector<int> cen;
void reset(){
n=0;
graph.clear(),graph.resize(0);
memset(pa,0,sizeof(pa));
memset(sz,0,sizeof(sz));
memset(spe,false,sizeof(spe));
cen.clear(),cen.resize(0);
memset(insub,false,sizeof(insub));
}
void setup(int u,int p){
sz[u]=1;
for(int v:graph[u]){
if(v!=p){
setup(v,u);
sz[u]+=sz[v];
}
}
}
void getcen(int u,int p,int n){
bool flag=true;
if(2*(n-sz[u])>n){
flag=false;
}
for(int v:graph[u]){
if(v!=p){
getcen(v,u,n);
if(2*sz[v]>n){
flag=false;
}
}
}
if(flag){
spe[u]=true;
cen.push_back(u);
}
}
void get_mark(int u,int p,vector<int> &t){
for(int v:graph[u]){
if(v!=p&&!spe[v]){
get_mark(v,u,t);
if(insub[v]){
insub[u]=true;
}
}
}
if(insub[u]){
t[u-1]=0;
}
else{
t[u-1]=1;
}
}
vector<int> mark(vector<pair<int,int>> edges,int safe){
reset();
n=edges.size()+1;
graph.resize(n+1);
for(int i=0;i<n-1;i++){
graph[edges[i].first].push_back(edges[i].second);
graph[edges[i].second].push_back(edges[i].first);
}
setup(1,-1);
getcen(1,-1,n);
insub[safe]=true;
vector<int> t(n);
for(int r:cen){
get_mark(r,-1,t);
}
return t;
}
void DFS(int u,int p){
pa[u]=p;
sz[u]=1;
for(int v:graph[u]){
if(v!=p&&!spe[v]){
DFS(v,u);
sz[u]+=sz[v];
}
}
}
bool cmp(int u,int v){
return (sz[u]>sz[v]);
}
void locate(vector<pair<int,int>> edges,int u,int t){
reset();
n=edges.size()+1;
graph.resize(n+1);
for(int i=0;i<n-1;i++){
graph[edges[i].first].push_back(edges[i].second);
graph[edges[i].second].push_back(edges[i].first);
}
setup(1,-1);
getcen(1,-1,n);
if(cen.size()==1){
DFS(cen[0],-1);
}
else{
DFS(cen[0],cen[1]);
DFS(cen[1],cen[0]);
}
for(int i=1;i<=n;i++){
sort(graph[i].begin(),graph[i].end(),cmp);
}
memset(spe,false,sizeof(spe));
while(true){
spe[u]=true;
if(t==1){
t=visit(pa[u]);
u=pa[u];
continue;
}
int nxt=-1;
for(int v:graph[u]){
if(v==pa[u]||spe[v]){
continue;
}
int bruh=visit(v);
if(!bruh){
nxt=v;
u=v,t=bruh;
break;
}
else{
visit(u);
}
}
if(nxt==-1){
return;
}
}
}
