#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
vector<int> g[90001];
vector<bool> used(90001);
map <pair<int,int>, int> mp;
vector<int> v, u , a(130001), d(130001);
int n , m , sm , bg , timer;
void bfs (int rt) {
queue <int> q;
q.push(rt);
while(!q.empty()){
int v = q.front();
q.pop();
used[v] = 1;
for(int k : g[v]){
if(used[k] != 0) continue;
a[timer++] = mp[{v , k}];
d[mp[{v , k}]] = k;
q.push(k);
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N; u = U; v = V, sm = A; bg = B;
m = u.size();
vector<int> vask;
for (int i = 0; i < m; i++) {
vask.pb(0);
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
mp[{u[i] , v[i]}] = mp[{v[i] , u[i]}] = i;
}
ll mn = ask(vask);
int l = 0 , r = n - 2;
bfs(0);
//cout<<d[4];
while (l < r) {
int mid = (l + r) / 2;
for (int i = 0; i <= mid; i++) {
vask[a[i]] = 0;
}
for (int i = mid + 1; i <= r; i++) {
vask[a[i]] = 1;
//cout<<a[i]<" ";
}
ll curs = ask(vask);
if (curs > mn) l = mid + 1;
else r = mid;
}
//cout<<d[a[l]];
answer(d[a[l]] , 0);
}
