#include "incursion.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FOR1(i, k, n) for(int i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "wtf.inp"
#define output "wtf.out"
#define rf freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 65537;
const int base1 = 31;
const int SZ = 320;
const ll INF = 1e18;
const long double EPS = 1e-9;
void add(int &a, int b)
{
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r)
{
return uniform_int_distribution<int>(l, r) (rd);
}
double rand(double l, double r)
{
return uniform_real_distribution<double>(l, r) (rd);
}
vi adj[maxn];
int sz[maxn];
int depth[maxn];
int root, par[maxn];
bool used[maxn];
int vertex;
vi col;
void DFS(int u)
{
sz[u] = 1;
if(depth[u] > depth[root])
root = u;
for(auto v : adj[u])
{
if(v == par[u])
continue;
depth[v] = depth[u] + 1;
par[v] = u;
DFS(v);
sz[u] += sz[v];
}
}
vector<int> mark(vector<pair<int, int>> edge, int safe) {
int n = edge.size() + 1;
FOR(i, 1, n)
adj[i].clear();
for(auto x : edge)
{
adj[x.fi].pb(x.se);
adj[x.se].pb(x.fi);
}
depth[1] = 0;
par[1] = 0;
root = 1;
FOR(i, 1, n)
par[i] = depth[i] = 0;
DFS(1);
depth[root] = 0, par[root] = 0;
int id = root;
FOR(i, 1, n)
par[i] = depth[i] = 0;
DFS(id);
vi diameter;
while(root != id)
{
diameter.pb(root);
root = par[root];
}
diameter.pb(id);
int vt;
if((int)diameter.size() % 2)
{
int len = diameter.size();
int mid = len / 2;
vt = diameter[mid];
}
else
{
int len = diameter.size();
int mid = len / 2;
vt = diameter[mid];
}
depth[vt] = 0;
FOR(i, 1, n)
par[i] = depth[i] = 0;
DFS(vt);
vi ans;
FOR(i, 1, n)
ans.pb(0);
while(safe != vt)
{
ans[safe - 1] = 1;
safe = par[safe];
}
ans[vt - 1] = 1;
return ans;
}
bool cmp(int x, int y)
{
return sz[x] > sz[y];
}
//int visit(int x)
//{
// vertex = x;
// return col[x - 1];
//}
void locate(vector<pair<int, int>>edge, int curr, int t) {
int n = edge.size() + 1;
FOR(i, 1, n)
used[i] = 0;
FOR(i, 1, n)
adj[i].clear();
for(auto x : edge)
{
adj[x.fi].pb(x.se);
adj[x.se].pb(x.fi);
}
depth[1] = 0;
par[1] = 0;
root = 1;
FOR(i, 1, n)
par[i] = 0;
DFS(1);
depth[root] = 0, par[root] = 0;
int id = root;
FOR(i, 1, n)
par[i] = 0;
DFS(id);
vi diameter;
while(root != id)
{
diameter.pb(root);
root = par[root];
}
diameter.pb(id);
int vt;
if(diameter.size() % 2)
{
int len = diameter.size();
int mid = len / 2;
vt = diameter[mid];
}
else
{
int len = diameter.size();
int mid = len / 2;
vt = diameter[mid];
}
depth[vt] = 0;
FOR(i, 1, n)
par[i] = depth[i] = 0;
DFS(vt);
while(t != 1)
{
used[curr] = 1;
if(curr == vt)
break;
t = visit(par[curr]);
curr = par[curr];
}
if(curr == vt && t == 0)
{
int len = diameter.size();
int mid = len / 2 - 1;
vt = diameter[mid];
t = visit(vt);
curr = vt;
}
int tam = adj[curr][0];
while(1)
{
visit(tam);
visit(curr);
}
int dem = 0;
while(1)
{
bool ok = 0;
vi child;
for(auto v : adj[curr])
{
if(v == par[curr] || used[v])
continue;
child.pb(v);
}
if(child.empty())
return;
sort(child.begin(), child.end(), cmp);
for(auto v : child)
{
t = visit(v);
if(t == 1)
{
curr = v;
ok = 1;
break;
}
else
{
used[v] = 1;
t = visit(curr);
dem++;
if(dem > 15)
{
while(1)
{
visit(v);
visit(curr);
}
return;
}
}
}
if(!ok)
break;
}
// cout << vertex << "t\n";
return;
}
//int main()
//{
// vii edge;
// int n = 10;
// edge.pb({1, 2});
// edge.pb({2, 3});
// edge.pb({1, 4});
// edge.pb({1, 5});
// edge.pb({5, 6});
// edge.pb({5, 7});
// edge.pb({2, 8});
// col = mark(edge, 7);
// vertex = 3;
// locate(edge, vertex, col[vertex - 1]);
// re;
//}
