#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
const int NM = 50000;
vector<int> vec[NM];
int sz[NM], papa[NM];
void dfs(int nod, int tata) {
papa[nod] = tata;
sz[nod] = 1;
for (auto &i : vec[nod]) {
if (i == tata)
continue;
dfs(i, nod);
sz[nod] += sz[i];
}
}
int find_centroid(int nod, int papa1, int target) {
for (auto i : vec[nod]) {
if (i == papa1)
continue;
if (sz[i] >= target)
return find_centroid(i, nod, target);
}
return nod;
}
vector<int> mark(vector<pair<int, int>> vp, int seif) {
int n = vp.size() + 1;
for (auto [u, v] : vp) {
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(1, 0);
int c = find_centroid(1, 0, (sz[1] + 1) / 2);
dfs(c, 0);
vector<int> ans(n);
ans[seif - 1] = 1;
while (seif != c) {
seif = papa[seif];
ans[seif - 1] = 1;
}
int c2 = -1;
for (auto i : vec[c]) {
if (sz[i] == (n + 1) / 2) {
c2 = i;
}
}
if (c2 != -1 && ans[c2] == 1)
ans[c] = 0;
return ans;
}
void locate(vector<pair<int, int>> vp, int pos, int nrt) {
int n = vp.size() + 1;
for (int i = 1; i <= n; i ++)
vec[i].clear();
for (auto [u, v] : vp) {
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(1, 0);
int c = find_centroid(1, 0, (sz[1] + 1) / 2);
dfs(c, 0);
int c2 = -1;
for (auto i : vec[c]) {
if (sz[i] == (n + 1) / 2) {
c2 = i;
}
}
if (c2 == -1) {
vec[c].push_back(c);
}
for (int i = 1; i <= n; i ++)
sort(vec[i].begin(), vec[i].end(), [&] (int a, int b) {
return sz[a] > sz[b];
});
while (nrt == 0) {
nrt = visit(vec[pos][0]);
pos = vec[pos][0];
}
//de acu incep in jos
while (1) {
bool ok = 0;
for (int i = 1; i < (int)vec[pos].size(); i ++) {
int nrtt = visit(vec[pos][i]);
if (nrtt == 0) {
visit(pos);
} else {
ok = 1;
pos = vec[pos][i];
nrt = nrtt;
break;
}
}
if (!ok) {
break;
}
}
}
