#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int maxn = 45003;
int n;
vector<int> rel[maxn];
void get_dist (int u, int p, vector<int> &dist) {
for (auto v : rel[u]) {
if (v == p) continue;
dist[v] = dist[u] + 1;
get_dist(v, u, dist);
}
}
int dfs1 (int u, int p, vector<int> &depth) {
int best = u;
for (auto v : rel[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
if (int ans = dfs1(v, u, depth); depth[ans] > depth[best]) best = ans;
}
return best;
}
bool dfs2 (int u, int p, int x, vector<int> &ans) {
ans.push_back(u);
if (u == x) return 1;
for (auto v : rel[u]) {
if (v == p) continue;
if (dfs2(v, u, x, ans)) return 1;
}
ans.pop_back();
return 0;
}
pair<int, int> get_centers () {
vector<int> depth(n, 0);
int u = dfs1(1, 1, depth);
depth[u] = 0;
int v = dfs1(u, u, depth);
vector<int> ans;
dfs2(u, u, v, ans);
int c1 = ans[(ans.size() - 1) / 2];
int c2 = ans[(ans.size()) / 2];
return {c1, c2};
}
void build_graph (vector<pair<int, int>> &ar) {
for (int i = 0; i < ar.size(); i++) {
auto [u, v] = ar[i];
u--; v--;
rel[u].push_back(v);
rel[v].push_back(u);
}
}
bool equal_vec (vector<int> &a, vector<int> &b) {
for (int i = 0; i < a.size(); i++) {
if (a[i] != b[i]) return 0;
}
return 1;
}
const vector<int> mods = {1, 0, 1, 1, 0, 0};
vector<int> mark(vector<pair<int, int>> ar, int safe) {
safe--;
n = ar.size() + 1;
build_graph(ar);
auto [c1, c2] = get_centers();
vector<int> dist(n, 0);
get_dist(safe, safe, dist);
if (dist[c1] > dist[c2]) swap(c1, c2);
vector<int> path;
dfs2(safe, safe, c1, path);
vector<int> vals(n, 0);
for (int i = 0; i < path.size(); i++) {
vals[path[i]] = 1;
}
return vals;
}
map<int, int> ties;
int get_tie (int r) {
if (ties.count(r)) return ties[r];
assert((false));
}
int my_visit (int v) {
int val = visit(v + 1);
ties[v] = val;
return val;
}
vector<int> walk (vector<int> path) {
vector<int> resp;
for (auto v : path) {
int val = my_visit(v);
resp.push_back(val);
}
return resp;
}
vector<int> sz(maxn, 0);
void size_dfs (int u, int p) {
sz[u] = 1;
for (auto v : rel[u]) {
if (v == p) continue;
size_dfs(v, u);
sz[u] += sz[v];
}
}
int walk_the_hard_path (int u, int p) {
for (auto v : rel[u]) {
if (v == p) continue;
int c = my_visit(v);
if (c == 1) return walk_the_hard_path(v, u);
my_visit(u);
}
return u;
}
void locate(vector<pair<int, int>> ar, int cur, int cur_ties) {
cur--;
for (int i = 0; i < maxn; i++) {
rel[i].clear();
}
n = ar.size() + 1;
build_graph(ar);
auto [c1, c2] = get_centers();
vector<int> dist1(n, 0);
get_dist(c1, c1, dist1);
vector<int> dist2(n, 0);
get_dist(c2, c2, dist2);
int my_root;
int other_root;
if (dist1[cur] > dist2[cur]) {
my_root = c2;
other_root = c1;
} else {
my_root = c1;
other_root = c2;
}
vector<int> path;
dfs2(cur, cur, my_root, path);
path.erase(path.begin());
walk(path);
cur = my_root;
if (get_tie(my_root) == 0 && my_root == other_root) return;
if (get_tie(my_root) == 0 && my_root != other_root) {
walk({other_root});
cur = other_root;
swap(my_root, other_root);
}
size_dfs(my_root, other_root);
if (walk_the_hard_path(my_root, other_root) == my_root) {
assert((get_tie(my_root) == 1));
walk({other_root});
}
return;
}
