#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int cnt = 0;
int n;
vector<int> G[100005];
int p[100005],fr[100005];
int l[100005],s[100005];
/*int ou = 0;
bool query(vector<int> v)
{
for(auto it : v)
{
if(it==ou)
{
return true;
}
}
return false;
}
*/
void dfs(int nod, int dad = 0)
{
p[++cnt] = nod;
l[nod] = cnt;
for(auto it : G[nod])
{
if(it==dad)
{
continue;
}
dfs(it,nod);
p[++cnt] = nod;
}
}
vector<int> get_query(int st, int dr)
{
vector<int> rez;
for(int i=st;i<=dr;i++)
{
if(!fr[p[i]])
{
rez.push_back(p[i]);
}
++fr[p[i]];
}
for(int i=st;i<=dr;i++)
{
fr[p[i]] = 0;
}
return rez;
}
bool cmp(int a, int b)
{
return l[a] < l[b];
}
int findEgg(int N, vector<pair<int,int>> e)
{
n = N;
for(auto it : e)
{
int x = it.first;
int y = it.second;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
for(int i=1;i<=n;i++)
{
s[i] = i;
}
sort(s+1,s+n+1,cmp);
int st = 1;
int dr = n;
while(st<dr)
{
int mij = (st+dr)>>1;
vector<int> q = get_query(l[s[st]],l[s[mij+1]]-1);
if(query(q))
{
dr = mij;
}
else
{
st = mij+1;
}
}
cnt = 0;
for(int i=1;i<=n;i++)
{
G[i].clear();
}
return s[st];
}
/*int main()
{
int n;
cin>>n>>ou;
vector<pair<int,int>> e;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
e.push_back({x,y});
}
cout<<findEgg(n,e);
return 0;
}
*/
