#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void find_pair(int n, std::vector<int> u, std::vector<int> v, int a, int b) {
int m = u.size();
vector<int> w(m,0);
int length = ask(w)/a;
ll l=1,r=m;
while (l<r){
ll mid = (l+r)>>1;
for (int i=0;i<m;i++) w[i] = 0;
for (int i=0;i<mid;i++){
w[i] = 1;
}
if (ask(w) > length*a){
r=mid;
}
else l=mid+1;
}
l--;
for (int i=0;i<l;i++) w[i] = 1;
vector<pair<ll,ll>> adj[n];
for (int i=l;i<m;i++){
adj[u[i]].push_back({v[i],i});
adj[v[i]].push_back({u[i],i});
}
ll dist[n];
memset(dist,-1,sizeof(dist));
ll root = u[l];
queue<pair<ll,ll>> bfs;
bfs.push({root,0});
ll visited[n];
memset(visited,0,sizeof(visited));
visited[root] = 1;
while (!bfs.empty()){
ll x = bfs.front().first, d = bfs.front().second;
if (dist[x] != -1 && dist[x] <= d) continue;
dist[x] = d;
bfs.pop();
for (auto nb:adj[x]){
ll nx = nb.first;
if (visited[nx]) continue;
bfs.push({nx,d+1});
visited[nx] = 1;
}
}
ll dist2[n];
memset(dist2,-1,sizeof(dist2));
memset(visited,0,sizeof(visited));
root = v[l];
bfs.push({root,0});
visited[root] = 1;
while (!bfs.empty()){
ll x = bfs.front().first, d = bfs.front().second;
if (dist2[x] != -1 && dist2[x] <= d) continue;
dist2[x] = d;
bfs.pop();
for (auto nb:adj[x]){
ll nx = nb.first;
if (visited[nx]) continue;
bfs.push({nx,d+1});
visited[nx] = 1;
}
}
vector<pair<ll,ll>> left,right;
for (int i=0;i<n;i++){
if (dist[i] < dist2[i]) left.push_back({dist[i],i});
else if (dist[i] > dist2[i]) right.push_back({dist2[i],i});
}
sort(left.begin(),left.end(),greater<>());
sort(right.begin(),right.end(),greater<>());
vector<ll> ql,qr;
for (int i=0;i<left.size()-1;i++){
for (pair<ll,ll> nb:adj[left[i].second]){
if (left[i].first > dist[nb.first]) {
ql.push_back(nb.second);
break;
}
}
}
for (int i=0;i<right.size()-1;i++){
for (pair<ll,ll> nb:adj[right[i].second]){
if (right[i].first > dist2[nb.first]) {
qr.push_back(nb.second);
break;
}
}
}
ll l2=0,r2=left.size()-1;
while (l2<r2){
ll mid = (l2+r2)>>1;
for (int i=0;i<=mid;i++){
w[ql[i]] = 1;
}
if (ask(w) > length*a) r2=mid;
else l2=mid+1;
}
ll l3=0,r3=right.size()-1;
while (l3<r3){
ll mid = (l3+r3)>>1;
for (int i=0;i<=mid;i++){
w[qr[i]] = 1;
}
if (ask(w) > length*a) r3=mid;
else l3=mid+1;
}
//l2 l3 is the guys
/*
cout << l << "\n";
cout << left[l2].second << ' ' << right[l3].second << "\n";
for (int i=0;i<left.size();i++) cout << left[i].second << ' ';
cout << "\n";
for (int i=0;i<right.size();i++) cout << right[i].second << ' ';
cout << "\n";
for (int i=0;i<n;i++) cout << dist[i] << ' ' << dist2[i] << "\n";
*/
answer(left[l2].second, right[l3].second);
}
