#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
vector<int>adj[(int)9e4+5];
long long ask(const vector<int>&v);
void answer(int s, int t);
void find_pair(int n, vector<int> U, vector<int> V, int a, int b) {
int m = (int)U.size();
vector<int>AA(m,0);
long long ans = ask(AA);
long long dist = ans / a;
int l = 0, r = m-1;
int id;
while(l <= r) {
if(l == r) {
id = l;
break;
}
int mid = (l+r)/2;
vector<int>A(m,0);
for(int i = 0 ; i <= mid ; i++)
A[i] = 1;
if(ask(A) != ans) {
id = mid;
r = mid;
} else {
l = mid+1;
}
}
int f = U[id], s = V[id];
//cout << f << " " << s << "\n";
map<pair<int,int>,int>mp;
for(int i = 0 ; i < m ; i++) if(i != id)
adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]), mp[{U[i],V[i]}] = mp[{V[i],U[i]}] = i;
// now binary search each part
vector<vector<int>>d(n);
vector<vector<int>>h(n);
d[0].push_back(f);
h[0].push_back(id);
queue<int>q;
q.push(f);
vector<bool>vis(n,0);
vis[f] = 1;
int D = 0;
while(!q.empty()) {
int sz = q.size();
while(sz--) {
int node = q.front();
q.pop();
vis[node] = 1;
for(auto z : adj[node]) {
if(!vis[z])
q.push(z), d[D+1].push_back(z), h[D+1].push_back(mp[{node,z}]);
}
}
D++;
}
l = 0, r = dist+1;
int P = 0;
while(l <= r) {
int mid = (l+r)/2;
vector<int>B(m,0);
if(h[mid].empty()) {
r = mid-1;
continue;
}
for(int i = 0 ; i < h[mid].size() ; i++)
B[h[mid][i]] = 1;
if(ask(B) != ans)
P = mid, l = mid+1;
else
r = mid-1;
}
dist -= P;
dist++;
l = 0, r = d[P].size();
int LE = f;
while(l <= r) {
if(l == r) {
LE = d[P][l];
break;
}
int mid = (l+r)/2;
vector<int>B(m,0);
for(int i = 0 ; i <= mid ; i++)
B[h[P][i]] = 1;
if(ask(B) != ans)
LE = d[P][mid], r = mid;
else
l = mid+1;
}
////////////////////////////////
vector<vector<int>>d2(n);
vector<vector<int>>h2(n);
d2[0].push_back(s);
h2[0].push_back(id);
q.push(s);
vector<bool>vis2(n,0);
vis2[f] = 1;
D = 0;
while(!q.empty()) {
int sz = q.size();
while(sz--) {
int node = q.front();
q.pop();
vis2[node] = 1;
for(auto z : adj[node]) {
if(!vis2[z])
q.push(z), d2[D+1].push_back(z), h2[D+1].push_back(mp[{node,z}]);
}
}
D++;
}
l = 0, r = dist;
P = 0;
while(l <= r) {
int mid = (l+r)/2;
vector<int>B(m,0);
if(h2[mid].empty()) {
r = mid-1;
continue;
}
for(int i = 0 ; i < h2[mid].size() ; i++)
B[h2[mid][i]] = 1;
if(ask(B) != ans)
P = mid, l = mid+1;
else
r = mid-1;
}
l = 0, r = d2[P].size();
int RE = s;
while(l <= r) {
if(l == r) {
RE = d2[P][l];
break;
}
int mid = (l+r)/2;
vector<int>B(m,0);
for(int i = 0 ; i <= mid ; i++)
B[h2[P][i]] = 1;
if(ask(B) != ans)
RE = d2[P][mid], r = mid;
else
l = mid+1;
}
//cout << LE << " " << RE << "\n";
answer(LE, RE);
}
