#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
int m=u.size();
vector<int> scuza(m,1); vector<int> paiu;
ll dist = ask(scuza)/b;
vector<vector<pair<int,int>>> adj(n);
for (int i=0; i<m; ++i) {
adj[u[i]].push_back({v[i],i});
adj[v[i]].push_back({u[i],i});
}
vector<int> vis(n,0), d(n,0); vis[0]=1;
vector<int> edges;
queue<int> q; q.push(0);
while (!q.empty()) {
int u=q.front(); q.pop();
for (auto it:adj[u]) {
int v=it.first;
if (!vis[v]) {
vis[v]=1;
d[v]=d[u]+1;
edges.push_back(it.second);
q.push(v);
}
}
}
int l=0, r=edges.size()-1;
while (l<r) {
int mid=(l+r)>>1;
paiu=scuza;
for (int i=0; i<=mid; ++i) paiu[edges[i]]=0;
ll x = ask(paiu);
if (x<1ll*dist*b) r=mid;
else l=mid+1;
}
int bgn;
if (d[u[edges[r]]]<d[v[edges[r]]]) bgn = u[edges[r]];
else bgn = v[edges[r]];
d.assign(n,0);
vis.assign(n,0);
vis[bgn]=1;
q.push(bgn);
edges.clear();
while (!q.empty()) {
int u=q.front(); q.pop();
for (auto it:adj[u]) {
int v=it.first;
if (!vis[v]) {
vis[v]=1;
d[v]=d[u]+1;
edges.push_back(it.second);
q.push(v);
}
}
}
l=0,r=edges.size()-1;
while (l<r) {
int mid=(l+r)>>1;
paiu=scuza;
for (int i=0; i<=mid; ++i) paiu[edges[i]]=0;
ll x = ask(paiu);
if (x>1ll*dist*a) l=mid+1;
else r=mid;
}
int s = d[u[edges[r]]]>d[v[edges[r]]] ? u[edges[r]] : v[edges[r]];
d.assign(n,0);
vis.assign(n,0);
vis[s]=1;
q.push(s);
vector<vector<int>>D(n);
while (!q.empty()) {
int u=q.front(); q.pop();
for (auto it:adj[u]) {
int v=it.first;
if (!vis[v]) {
vis[v]=1;
d[v]=d[u]+1;
D[d[v]].push_back(v);
q.push(v);
}
}
}
vector<int>amog=D[dist];
l=0, r=amog.size()-1;
while (l<r) {
int mid=(l+r)>>1;
paiu=scuza;
for (int i=0; i<=mid; ++i) for (auto it:adj[amog[i]]) {
int v=it.first;
if (d[v]==d[amog[i]]-1) paiu[it.second]=0;
}
ll x = ask(paiu);
if (x<1ll*dist*b) r=mid;
else l=mid+1;
} //cout<<s<<' '<<amog[r]<<'\n';
answer(s,amog[r]);
}
