#include <bits/stdc++.h>
#include "incursion.h"
using namespace std;
vector<int> g[100005], v[2];
int s[100005], a[2], hh, dd[100005], ll[100005], b[100005];
void dfs(int x, int p) {
s[x] = 1; ll[x] = p;
for (int w : g[x]) {
if (w == p) continue;
dfs(w, x);
s[x] += s[w];
}
}
bool dfs2(int x, int p, int h) {
if (hh == x) {
v[h].push_back(x);
return 1;
}
s[x] = 1;
for (int w : g[x]) {
if (w == p) continue;
if (dfs2(w, x, h)) {
v[h].push_back(x);
return 1;
}
}
return 0;
}
vector<int> mark(vector<pair<int, int>> e, int x) {
int n = 0, z = 0; hh = x;
for (auto w : e) {
g[w.first].push_back(w.second);
g[w.second].push_back(w.first);
n = max(n, w.first); n = max(n, w.second);
}
dfs(1, -1);
for (int i = 1; i <= n; i++) {
if (s[i] < (n + 1) / 2) continue;
int fl = 0;
for (int w : g[i]) {
if (s[w] > n / 2 && ll[i] != w) {
fl = 1;
}
}
if (fl == 0) {
a[z++] = i;
}
}
for (int i = 0; i < z; i++) {
v[i].clear();
dfs2(a[i], -1, i);
}
if (z > 1 && v[0].size() > v[1].size()) swap(v[0], v[1]);
vector<int> res(n, 0);
for (int w : v[0]) res[w - 1] = 1;
for (int i = 1; i <= n; i++) g[i].clear();
return res;
}
bool cmp(int aa, int bb) {
return s[aa] > s[bb];
}
void locate(vector<pair<int, int>> e, int cur, int l) {
int n = 0;
for (auto w : e) {
g[w.first].push_back(w.second);
g[w.second].push_back(w.first);
n = max(n, w.first); n = max(n, w.second);
}
dfs(1, -1);
int h = 0;
for (int i = 1; i <= n; i++) {
if (s[i] < (n + 1) / 2) continue;
int fl = 0;
for (int w : g[i]) {
if (s[w] > n / 2 && ll[i] != w) fl = 1;
}
if (fl == 0) {
h = i;
break;
}
}
dfs(h, -1);
while (1) {
dd[cur] = 1;
if (l == 0 && cur != h) {
l = visit(ll[cur]); cur = ll[cur];
continue;
}
vector<int> v;
for (int w : g[cur]) {
if (dd[w] || w == ll[cur]) continue;
v.push_back(w);
}
/*cout << cur << " " << g[cur][0] << '\n';
for (int w : v) cout << w << " ";
cout << '\n';*/
sort(v.begin(), v.end(), cmp);
if (v.empty()) break;
cur = v[0];
l = visit(cur);
}
for (int i = 1; i <= n; i++) {
g[i].clear(); dd[i] = 0;
}
}
