#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define DUZO 1000000000000000000
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
vvi g;
vi ak;
vi out;
int mid;
int ile_poszlo;
vi pyt;
/*int query(vi a) {
for (int ele: a) {
if (ele == 3) return 1;
}
return 0;
}*/
void dfs_pyt(int v, int p) {
if (ile_poszlo >= mid) return;
if (ak[v]) {
ile_poszlo++;
pyt.pb(v);
}
for (int u: g[v]) {
if (u == p || out[v]) continue;
dfs_pyt(u, v);
}
}
int findEgg(int n, vector<pii> kr) {
g = {};
g.resize(n + 1);
for (auto [u, v]: kr) {
g[u].pb(v);
g[v].pb(u);
}
ak = {};
out = {};
out.resize(n+ 1, 0);
ak.resize(n + 1, 1); //czy jest w potencjalnym solvie
unordered_set<int> zb;
f(i, 1, n+ 1) zb.insert(i);
while (sz(zb)>1) {
mid = sz(zb)/2;
pyt = {};
ile_poszlo = 0;
dfs_pyt(*(zb.begin()), 0);
int val = query(pyt);
if (val) {
f(i, 1, n+ 1) ak[i] = 0;
unordered_set<int> lol;
for (int ele: pyt) {
lol.insert(ele);
ak[ele] = 1;
}
zb= lol;
} else {
for (int ele: pyt) {
zb.erase(ele);
ak[ele] = 0;
}
}
f(i, 1, n+ 1) {
if (ak[i]) continue;
bool git = false;
for (int ele: g[i]) {
if (ak[ele]) {
git = true;
}
}
if (!git) out[i] = 1;
}
}
return *(zb.begin());
}
/*int main() {
int n = 7;
vector<pii> kr = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {4, 6}, {3, 7}};
cout << findEgg(n, kr) << "\n";
}*/
