#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
vector<int> g[90001] , ans;
vector<bool> used(90001);
map <pair<int,int>, int> mp;
vector<int> vask;
vector<int> v, u , a(130001), d(130001);
int n , m , sm , bg;
ll mn;
void bfs (int rt) {
queue <int> q;
q.push(rt);
for (int i = 0; i < n; i++)
used[i] = 0;
int timer = 0;
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_ans(int rt) {
int l = 0 , r = n - 2;
bfs(rt);
//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;
}
ans.pb(d[a[l]]);
}
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();
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;
}
mn = ask(vask);
ll l = 0, r = n - 1;
while (l < r) {
ll mid = (l + r) / 2;
for (int i = 0; i < m; i++)
vask[i] = 1;
for (int i = 0; i <= mid; i++) {
for (auto k : g[i]) {
vask[mp[{i , k}]] = 0;
}
}
ll curs = ask(vask);
if (curs == mn) r = mid;
else l = mid + 1;
}
find_ans(l);
//cout<<ans[0];
find_ans(ans[0]);
//cout<<ans[1];
//cout<<d[a[l]];
answer(ans[0] , ans[1]);
}
