#include "incursion.h"
#include <bits/stdc++.h>
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll sub[50000];
vector<ll> edges[50000];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];
ll n;
void dfs(ll a, ll p, ll d){
depth[a] = d;
par[a] = p;
sub[a] = 1;
for (auto&i : edges[a]){
if (i != p) dfs(i,a,d+1), sub[a] += sub[i];
}
}
ll centfind(ll a, ll p){
for (auto&i : edges[a]){
if (i!=p && sub[i] > n/2) return centfind(i, a);
}
return a;
}
vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
n = (ll)F.size()+1;
vector<int> ties(n);
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll cent = centfind(1, -1);
dfs(cent, -1, 0);
while (safe != -1){
ties[safe-1] = 1;
safe = par[safe];
}
return ties;
}
bool cmp(ll a, ll b){
return sub[a] < sub[b];
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
n = (ll)F.size()+1;
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll cent = centfind(1, -1);
dfs(cent, -1, 0);
visited[curr] = 1;
//cout << cent << endl;
while (t != 1 && curr != cent){
t = visit(par[curr]);
curr = par[curr];
visited[curr] = 1;
}
while (1){
visited[curr] = 1;
if (t==0 && curr!=cent){
t = visit(par[curr]);
curr = par[curr];
continue;
}
sort(edges[curr].begin(), edges[curr].end(), cmp);
reverse(edges[curr].begin(), edges[curr].end());
bool done = false;
for (auto&i : edges[curr]){
if (i==par[curr]) continue;
if (!visited[i]){
visited[i] = true;
t = visit(i);
curr = i;
done = true;
break;
}
}
if (!done){
return;
}
}
}
