#include <bits/stdc++.h>
#include "incursion.h"
#define ll int
#define vi vector<ll>
#define pp pair<ll, ll>
#define vvi vector<vi>
#define inf 1000000000
using namespace std;
void dfs1(ll u, ll par,vvi& edges, vi& subTree, vi &parent){
parent[u] = par;
for(ll v : edges[u]){
if(v == par) continue;
dfs1(v, u, edges, subTree, parent);
subTree[u] += subTree[v];
}
return;
}
void move(ll u, ll v, vi& subTree){
ll y = subTree[v];
ll n = subTree.size();
subTree[v] = n;
subTree[u] = n - y;
}
pp find(vvi edges){
ll n = edges.size();
vi subTree(n, 1);
vi parent(n, -1);
dfs1(0, 0, edges, subTree, parent);
ll u = 0;
while(true){
bool centroid = true;
for(ll v : edges[u]){
if(subTree[v] > n / 2){
centroid = false;
move(u, v, subTree);
u = v;
break;
}
}
if(centroid) break;
}
ll secC = -1;
ll mxSub = -1;
for(ll v : edges[u]){
if(subTree[v] > mxSub){
mxSub = subTree[v];
secC = v;
}
}
move(u, secC, subTree);
bool centroid = true;
for(ll v : edges[u]){
if(subTree[v] > n / 2){
centroid = false;
move(u, v, subTree);
break;
}
}
move(secC, u, subTree);
if(!centroid) secC = u;
return {u, secC};
}
void dfs2(ll u, vvi& edges, vi& was, vi& depth){
was[u] = 1;
for(ll v : edges[u]){
if(was[v] == 1) continue;
depth[v] = depth[u] + 1;
dfs2(v, edges, was, depth);
}
return;
}
void dfs3(ll u, ll par, vvi& edges, vi& depth, vi &ans){
for(ll v : edges[u]){
if(v == par) continue;
if(depth[v] < depth[u]) ans[v] = 1;
else ans[v] = 0;
dfs3(v, u, edges, depth, ans);
}
return;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
ll n = F.size() + 1;
safe--;
vvi edges(n);
for(pp x : F){
x.first--;
x.second--;
edges[x.first].push_back(x.second);
edges[x.second].push_back(x.first);
}
pp cent = find(edges);
vi depth(n, 0);
vi was(n, 0);
was[cent.first] = 1;
was[cent.second] = 1;
dfs2(cent.first, edges, was, depth);
dfs2(cent.second, edges, was, depth);
vi ans(n, 0);
dfs3(safe, -1, edges, depth, ans);
ans[safe] = 1;
return ans;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
curr--;
ll n = F.size() + 1;
vvi edges(n);
for(pp x : F){
x.first--;
x.second--;
edges[x.first].push_back(x.second);
edges[x.second].push_back(x.first);
}
pp cent = find(edges);
vi depth(n, 0);
vi was(n, 0);
was[cent.first] = 1;
was[cent.second] = 1;
dfs2(cent.first, edges, was, depth);
dfs2(cent.second, edges, was, depth);
vi parent(n, -1);
vi centS(n, 1);
dfs1(cent.first, cent.second, edges, centS, parent);
if(cent.first != cent.second) dfs1(cent.second, cent.first, edges, centS, parent);
vi cnt(n, 0);
while(true){
cnt[curr]++;
if(t == 0){
t = visit(parent[curr] + 1);
curr = parent[curr];
}else if(t == 1){
ll mxS = -1;
ll nextSon = -1;
for(ll son : edges[curr]){
if(son == parent[curr]) continue;
if(cnt[son] > 0) continue;
if(centS[son] > mxS){
mxS = centS[son];
nextSon = son;
}
}
if(nextSon == -1) break;
t = visit(nextSon + 1);
curr = nextSon;
}
}
return;
}
