#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define print(l) for(auto i:l) cout<<i<<" ";cout<<endl;
#define input(t,l,n) vector<t>l(n);for(int i = 0;i<n;i++)cin>>l[i];
// #define int long long
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define all(l) l.begin(),l.end()
#define pii pair<int,int>
#define fi first
#define se second
vector<vector<int>>adj,sub;
vector<int>pa;
void dfs(int v,int par){
sub[v].pb(v);
pa[v] = par;
for(int i:adj[v]){
if(i == par)continue;
dfs(i,v);
for(int j:sub[i]){
sub[v].pb(j);
}
// sub[v]+=sub[i];
}
}
int findEgg (int N, vector < pair < int, int > > bridges){
adj.clear();
sub.clear();
pa.clear();
pa.resize(N+1);
sub.resize(N+1);
adj.resize(N+1);
for(auto i:bridges){
adj[i.fi].pb(i.se);
adj[i.se].pb(i.fi);
}
dfs(1,1);
vector<vector<pair<int,int>>>ord(N+1);
for(int i = 1;i<=N;i++){
for(int j:adj[i]){
if(j == pa[i])continue;
ord[i].pb({(int)sub[j].size(),j});
}
sort(all(ord[i]));
}
int cur = 1;
int t = 10;
while(t--){
int f = 0;
for(auto i:ord[cur]){
int x = query(sub[i.se]);
if(x == 1){
f = 1;
cur = i.se;
break;
}
}
if(!f)break;
}
return cur;
}
