#include <bits/stdc++.h>
#include "grader.h"
//#include "grader.cpp"
using namespace std;
const int TP=533;
set<int> ma[TP];
int n,sub[TP],deg[TP],par[TP];
set<int> rem;
int sz,fv=-1;
vector<int> cur;
void compute(int x,int p)
{
// cout<<"AT "<<x<<' '<<p<<endl;
for(auto y:ma[x])
{
if(y==p)continue;
compute(y,x);
}
cur.push_back(x);
}
void dfs_(int x,int p=-1)
{
sub[x]=1;
par[x]=p;
for(auto y:ma[x])
{
if(y==p)continue;
dfs_(y,x);
sub[x]+=sub[y];
}
// if(sub[x]==(sz/2))
// {
// fv=x;
// }
}
int find_centriod(int x,int p=-1)
{
for(auto y:ma[x])
{
if(y!=p and sub[y]>(sz/2))
{
sub[x]-=sub[y];
sub[y]+=sub[x];
return find_centriod(y,x);
}
}
return x;
}
int findEgg (int N, vector < pair < int, int > > edge)
{
n=N;
for(int i=0;i<=n;i++)ma[i].clear();
for(int i=0;i<n-1;i++)
{
ma[edge[i].first].insert(edge[i].second);
ma[edge[i].second].insert(edge[i].first);
}
rem.clear();
for(int i=1;i<=n;i++)
{
rem.insert(i);
}
while(rem.size()>1) // 9 time
{
sz=rem.size();
// cout<<"Cur "<<sz<<endl;
int x=*begin(rem);
// cout<<"X: "<<x<<" SZ done"<<endl;
// for(auto x:rem)
// {
dfs_(x);
pair<int,int> mi={1e9,1e9};
for(auto y:rem)
{
bitset<520> pos;
pos[1]=1; // only y
for(auto oe:ma[y])
{
if(oe==par[y])continue;
pos|=(pos<<sub[oe]); // y along some other subtree
}
if(par[y]!=-1)
{
pos|=(pos<<(sz-sub[y])); // y along with other subtree
}
// 2x we need to find connected x node
// 2x+1 x x+1
// cout<<"Compute bitset "<<y<<endl;
int asy=pos._Find_next((sz/2)-1);
mi=min(mi,{asy,y});
}
int asy=mi.first;
int y=mi.second;
// cout<<"Copmuting dp"<<endl;
// cout<<"Min "<<asy<<' '<<y<<endl;
vector<vector<int>> dp(530);
dp[1]={y};
for(auto oe:ma[y])
{
if(oe==par[y])continue;
for(int q=519-sub[oe];q>=0;q--)
{
if(dp[q].size()>0)
{
dp[q+sub[oe]]=dp[q];
dp[q+sub[oe]].push_back(oe);
}
}
}
if(par[y]!=-1)
{
for(int q=519-(sz-sub[y]);q>=0;q--)
{
if(dp[q].size()>0)
{
dp[q+(sz-sub[y])]=dp[q];
dp[q+(sz-sub[y])].push_back(par[y]);
}
}
}
// cout<<"Dp done"<<endl;
int zy=asy;
set<int> want(begin(dp[zy]),end(dp[zy])); // we surely take y
// while(zy>0)
// {
// cout<<"Vertex "<<dp[zy]<<" added to answer"<<endl;
// want.insert(dp[zy]);
// int yp=dp[zy];
// if(yp==y)
// {
// cout<<"SELF "<<1<<endl;
// zy-=1;
// }
// else if(yp==par[y])
// {
// cout<<"Sizep "<<sz-sub[y]<<endl;
// zy-=(sz-sub[y]);
// }
// else
// {
// cout<<"Sizec "<<sub[yp]<<endl;
// zy-=sub[yp];
// }
// }
cur.clear();
cur.push_back(y);
cur.push_back(x);
// cout<<"WANT: ";
// for(auto tp:want)cout<<tp<<' ';
// cout<<endl;
// cout<<"Subtree "<<endl;
for(auto yp:ma[y])
{
if(want.find(yp)!=want.end())
{
compute(yp,y);
}
}
// cout<<"CUR: ";
// for(auto i:cur)cout<<i<<' ';
// cout<<endl;
if(query(cur))
{
sort(begin(cur),end(cur));
for(auto xa:rem)
{
auto it=lower_bound(begin(cur),end(cur),xa);
if(it==end(cur) or *it!=xa)
{
for(auto y:ma[xa])
{
ma[y].erase(xa);
}
ma[xa].clear();
// we will delete this
// int x=y;
}
}
rem.clear();
for(auto x:cur)rem.insert(x);
}
else
{
for(auto xa:cur)
{
for(auto y:ma[xa])
{
ma[y].erase(xa);
}
ma[xa].clear();
rem.erase(xa);
}
}
cur.clear();
// break;
// }
}
return *begin(rem);
}
// int findEgg (int N, vector < pair < int, int > > edge)
// {
// n=N;
// for(int i=0;i<n-1;i++)
// {
// deg[edge[i].first]++;
// deg[edge[i].second]++;
// }
// for(int i=1;i<=n;i++)
// {
// if(query({i}))return i;
// }
// return 0;
// }
