#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int maxn = 1e5;
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> vals(n, 0);
if (c1 == safe) {
vals[c1] = 0;
if (c2 != c1) vals[c2] = 1;
return vals;
}
if (c2 == safe) assert(false);
vector<int> path;
dfs2(safe, safe, c1, path);
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<bool> prohibited (maxn, 0);
vector<int> walk (vector<int> path) {
vector<int> resp;
for (auto v : path) {
prohibited[v] = 1;
int val = my_visit(v);
resp.push_back(val);
if (val == 1) return resp;
}
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, vector<int> &dist) {
vector<pair<int, int>> priority;
for (auto v : rel[u]) {
if (prohibited[v]) continue;
if (dist[v] < dist[u]) continue;
if (v == p) continue;
priority.push_back({sz[v], v});
}
sort(priority.begin(), priority.end());
reverse(priority.begin(), priority.end());
for (auto [_, v] : priority) {
int c = my_visit(v);
if (c == 1) return walk_the_hard_path(v, u, dist);
my_visit(u);
}
return u;
}
void locate(vector<pair<int, int>> ar, int cur, int cur_ties) {
cur--;
prohibited[cur] = 1;
ties[cur] = cur_ties;
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 = c1;
int other_root = c2;
if (dist1[cur] > dist2[cur]) {
dist1.swap(dist2);
swap(my_root, other_root);
}
if (cur_ties == 1 && cur != c1 && cur != c2) {
walk_the_hard_path(cur, cur, dist1);
return;
}
vector<int> path;
dfs2(cur, cur, my_root, path);
path.erase(path.begin());
vector<int> walked = walk(path);
cur = walked.size() == 0 ? cur : path[walked.size() - 1];
if (cur != my_root) {
walk_the_hard_path(cur, cur, dist1);
return;
}
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);
dist1.swap(dist2);
}
size_dfs(my_root, my_root);
int walking = walk_the_hard_path(my_root, my_root, dist1);
if (walking == my_root) {
assert((get_tie(my_root) == 1));
assert((my_root != other_root));
auto c = walk({other_root});
assert((c[0] == 0));
return;
}
return;
}
