#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<int,int>>> adj;
int m;
int n;
void find_pair(int N, vector<int> u, vector<int> v, int a, int b) {
n = N;
m = u.size();
adj.resize(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> edist(m, 0);
vector<int> dist(n,0);
vector<bool> vis(n, false);
vis[0] = true;
queue<int> q;
q.push(0);
while(!q.empty()) {
int v = q.front(); q.pop();
int d = dist[v];
for(auto &e : adj[v]) {
int id = e.second;
int u = e.first;
if(vis[u]) continue;
vis[u] = true;
dist[u] = d + 1;
edist[id] = d + 1;
q.push(u);
}
}
vector<int> empty(m, 0);
ll cw = ask(empty);
ll len = cw/a;
vector<pair<int,int>> S;
for(int i = 0; i < m; i++) {
S.push_back({edist[i], i});
}
sort(S.rbegin(), S.rend());
int lo = 0;
int hi = m;
while(hi - lo > 2) {
int p = (hi+lo)/2;
vector<int> Q(m, 0);
for(int j = 0; j <= p; j++) {
Q[S[j].second] = 1;
}
ll as = ask(Q);
if(as == cw) {
lo = p + 1;
} else {
hi = p;
}
}
int s = 0;
int fe = -1;
for(int y = lo; y <= hi; y++) {
vector<int> Q(m, 0);
for(int j = 0; j <= y; j++) {
Q[S[j].second] = 1;
}
ll as = ask(Q);
if(as > cw) {
fe = S[y].second;
break;
}
}
int t;
if(dist[u[fe]] == len) t = u[fe];
else t = v[fe];
answer(s,t);
}
