#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 5e4;
vector <ll> adj[MAXN + 5];
ll up[MAXN + 5], sz[MAXN + 5], N;
ll find_centroid(ll idx, ll par) {
for (auto i : adj[idx]) {
if (i != par && sz[i] > N / 2) {
return find_centroid(i, idx);
}
}
return idx;
}
void dfs(ll idx, ll par) {
sz[idx] = 1;
for (auto i : adj[idx]) {
if (i != par) {
up[i] = idx;
dfs(i, idx);
sz[idx] += sz[i];
}
}
}
vector <int> mark(vector <pair<int, int>> F, int safe) {
N = -1;
for (auto [i, j] : F) {
adj[i].push_back(j), adj[j].push_back(i);
N = max({N, (ll)i, (ll)j});
}
dfs(1, -1);
ll start = find_centroid(1, -1);
dfs(start, -1);
ll cur = safe;
vector <int> A(N);
while (cur != start) {
A[cur - 1] = 1;
cur = up[cur];
}
A[start - 1] = 1;
for (int i = 1; i <= N; i++) {
adj[i].clear();
up[i] = sz[i] = 0;
}
return A;
}
ll find_centroid_2(ll idx, ll par) {
bool found = 1;
for (auto i : adj[idx]) {
if (i != par && sz[i] > N / 2) {
found &= visit(i);
return find_centroid_2(i, idx);
}
}
if (!found) {
for (auto i : adj[idx]) {
if (i != par && sz[i] == N / 2) {
visit(i);
return i;
}
}
}
return idx;
}
void solve(ll idx, ll par) {
vector <ll> candidates;
for (auto i : adj[idx]) {
if (i != par) {
candidates.push_back(i);
}
}
sort(candidates.begin(), candidates.end(), [&](ll a, ll b){
return sz[a] > sz[b];
});
for (auto i : candidates) {
if (visit(i)) {
solve(i, idx);
break;
}
visit(idx);
}
}
void locate(vector <pair<int, int>> F, int curr, int t) {
N = -1;
for (auto [i, j] : F) {
adj[i].push_back(j), adj[j].push_back(i);
N = max({N, (ll)i, (ll)j});
}
dfs(curr, -1);
ll start = find_centroid_2(curr, -1);
solve(start, -1);
}
