#include "bits/stdc++.h"
#include "incursion.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
const int N = 5e4;
int n;
vector<int> g[N];
int dist[N], p[N], sz[N];
void dfs(int u, int pre = -1){
sz[u] = 1;
for(int v : g[u]){
if(v == pre)
continue;
dist[v] = dist[u] + 1;
p[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
vector<int> mark(vector<pii> F, int safe){
n = sz(F) + 1;
for(auto [u, v] : F){
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
int x = max_element(dist + 1, dist + n + 1) - dist;
dist[x] = 0;
dfs(x);
int y = max_element(dist + 1, dist + n + 1) - dist;
vector<int> diam;
while(true){
diam.push_back(y);
if(y == x)
break;
y = p[y];
}
dist[safe] = 0;
dfs(safe);
int root = -1;
if(sz(diam) & 1)
root = diam[sz(diam) / 2];
else{
int u = diam[sz(diam) / 2];
int v = diam[sz(diam) / 2 - 1];
root = (dist[u] < dist[v] ? u : v);
}
vector<int> color(n, 0);
while(true){
color[root - 1] = 1;
if(root == safe)
break;
root = p[root];
}
for(int i = 1; i <= n; ++i){
g[i].clear();
dist[i] = sz[i] = p[i] = 0;
}
return color;
}
void locate(vector<pii> F, int cur, int t){
n = sz(F) + 1;
debug(F);
for(auto [u, v] : F){
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
int x = max_element(dist + 1, dist + n + 1) - dist;
dist[x] = 0;
dfs(x);
int y = max_element(dist + 1, dist + n + 1) - dist;
vector<int> diam;
while(true){
diam.push_back(y);
if(y == x)
break;
y = p[y];
}
int root = diam[sz(diam) / 2];
dist[root] = 0;
p[root] = 0;
dfs(root);
for(int i = 1; i <= n; ++i){
sort(all(g[i]), [](int u, int v) -> bool{
return sz[u] > sz[v];
});
}
int pre = -1;
debug(cur, pre);
while(cur != root and !t){
pre = cur;
t = visit(p[cur]);
cur = p[cur];
}
debug(cur, root);
if(!t){
dist[cur] = 0;
p[cur] = 0;
dfs(cur);
for(int i = 1; i <= n; ++i){
sort(all(g[i]), [](int u, int v) -> bool{
return sz[u] > sz[v];
});
}
}
while(true){
bool cont = 0;
for(int v : g[cur]){
if(v == pre or v == p[cur])
continue;
int nxt = visit(v);
if(nxt){
cur = v;
cont = 1;
break;
}
else
visit(cur);
}
if(!cont)
return;
}
}
