// #define dak
#ifndef dak
#include "incursion.h"
#endif
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=45005;
int h[nx], par[nx], sz[nx], mp[nx];
vector<int> adj[nx], path, res;
void dfs(int p, int u)
{
for(int v:adj[u])
if(v!=p)
h[v]=h[u]+1, dfs(u, v);
}
bool go(int p, int u, int v)
{
if(u==v)
{
path.emplace_back(u);
return 1;
}
for(int c:adj[u])
if(c!=p && go(u, c, v))
{
path.emplace_back(u);
return 1;
}
return 0;
}
bool sus(int p, int u, int S)
{
if(u==S) return 1;
bool ok=0;
for(int v:adj[u])
if(v!=p)
ok|=sus(u, v, S);
return ok;
}
vector<int> mark(vector<ii> ed, int safe)
{
int n=ed.size();
n++;
int l=1;
h[1]=0;
for(int i = 1; i <= n; i++)
adj[i].clear();
for(auto it:ed)
adj[it.fi].emplace_back(it.se), adj[it.se].emplace_back(it.fi);
dfs(0, 1);
int r=1;
for(int i = 1; i <= n; i++)
if(h[i]>h[r])
r=i;
h[r]=0;
dfs(0, r);
for(int i = 1; i <= n; i++)
if(h[i]>h[l])
l=i;
path.clear();
go(0, l, r);
int root;
if(h[l]&1)
{
if(sus(path[h[l]/2+1], path[h[l]/2], safe))
root=path[h[l]/2];
else root=path[h[l]/2+1];
}
else root=path[h[l]/2];
res.assign(n, 0);
path.clear();
go(0, root, safe);
for(int u:path)
res[u-1]=1;
return res;
}
void dfs1(int p, int u)
{
sz[u]=1;
for(int v:adj[u])
if(v!=p)
par[v]=u, dfs1(u, v), sz[u]+=sz[v];
}
#ifdef dak
int visit(int u)
{
}
#endif
void find(int p, int u)
{
int bc=-1;
for(int v:adj[u])
{
if(v==p) continue;
if(bc==-1 || sz[bc]<sz[v])
bc=v;
}
for(int v:adj[u])
{
if(v==p || v==bc) continue;
if(visit(v)) return find(u, v);
visit(u);
}
if(bc!=-1)
{
if(visit(bc)) return find(u, bc);
visit(u);
}
}
void locate(vector<ii> ed, int cur, int C)
{
int n=ed.size();
n++;
int l=1;
h[1]=0;
for(int i = 1; i <= n; i++)
adj[i].clear(), mp[i]=-1;
mp[cur]=C;
for(auto it:ed)
adj[it.fi].emplace_back(it.se), adj[it.se].emplace_back(it.fi);
dfs(0, 1);
int r=1;
for(int i = 1; i <= n; i++)
if(h[i]>h[r])
r=i;
h[r]=0;
dfs(0, r);
for(int i = 1; i <= n; i++)
if(h[i]>h[l])
l=i;
path.clear();
go(0, l, r);
int root=path[h[l]/2];
for(int i = 1; i <= n; i++)
par[i]=0;
dfs1(0, root);
while(C==0 && cur!=root)
cur=par[cur], C=visit(cur);
if(C==0)
{
root=path[h[l]/2+1];
C=visit(root);
if(C==0) assert(0);
cur=root;
}
find(par[cur], cur);
}
