#include "highway.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<pair<int,int>> adj[N];
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
int m = u.size();
vector<int> w(m,0);
long long len = ask(w) / a;
int l = 0,r = m-1;
while(l < r){
int m = (l + r)/2;
for(int i = l;i<=m;i++){
w[i] = 1;
}
if(ask(w) != len * a){
for(int i = l;i<=m;i++){
w[i] = 0;
}
r = m;
}
else l = m + 1;
}
for(int i = 0;i<m;i++){
adj[u[i]].push_back({v[i],i});
adj[v[i]].push_back({u[i],i});
}
// cout << "LEN:";
// cout << len << endl;
// cout << "EDGE:";
// cout << u[l] << ' ' << v[l] << endl;
queue<int> q;
auto bfs = [&](int v){
vector<int> d(n,-1);
vector<int> par(n,-1);
queue<int> q;
q.push(v);
d[v] = 0;
while(q.size()){
auto tp = q.front();
q.pop();
for(auto u:adj[tp]){
if(d[u.first] == -1){
d[u.first] = d[tp] + 1;
par[u.first] = u.second;
q.push(u.first);
}
}
}
return make_pair(d,par);
};
auto x1 = bfs(u[l]);
auto x2 = bfs(v[l]);
vector<int> ord1;
vector<int> ord2;
for(int i = 0;i<n;i++){
if(x1.first[i] < x2.first[i]){
ord1.push_back(i);
}
if(x2.first[i] < x1.first[i]){
ord2.push_back(i);
}
}
sort(ord1.begin(),ord1.end(),[&](int a,int b){
return x1.first[a] < x1.first[b];
});
sort(ord2.begin(),ord2.end(),[&](int a,int b){
return x2.first[a] < x2.first[b];
});
// for(int i = 0;i<m;i++){
// if(w[i] == 0){
// cout << u[i] << ' ' << v[i] << endl;
// }
// }
int s = -1;
int t = -1;
l = 0, r = (int)ord1.size() - 1;
while(l < r){
int m = (l + r)/2;
for(int i = m+1;i<r;i++){
w[x1.second[ord1[i]]] = 1;
}
if(ask(w) == len * a){
r = m;
}
else{
for(int i = m+1;i<r;i++){
w[x1.second[ord1[i]]] = 0;
}
l = m+1;
}
}
s = ord1[l];
l = 0, r = (int)ord2.size() - 1;
while(l < r){
int m = (l + r)/2;
for(int i = m+1;i<r;i++){
w[x2.second[ord2[i]]] = 1;
}
if(ask(w) == len * a){
r = m;
}
else{
for(int i = m+1;i<r;i++){
w[x2.second[ord2[i]]] = 0;
}
l = m+1;
}
}
t = ord2[l];
answer(s,t);
}
/*
11 12 16 19 9 10
1 0
2 0
3 1
4 0
5 4
6 3
7 4
8 4
9 5
10 1
9 3
5 1
*/
