#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
struct node{
vector<pii> to;
int depth = 0, start = -1, with = -1;
};
vector<node> graph;
vector<int> s;
int getEdge(int l, int r, int M, ll dist){
if(l+1 == r) return l;
int m = (l+r)/2;
for(int i = l; i < r; i++) s[i] = 0;
for(int i = l; i < m; i++) s[i] = 1;
ll x = ask(s);
if(x == dist)
return getEdge(m, r, M, dist);
else
return getEdge(l, m, M, dist);
}
void BFS(int x, int y){
queue<int> q;
q.push(x), q.push(y);
graph[x].start = x, graph[y].start = y;
while(q.size() > 0){
int curr = q.front();
q.pop();
for(pii& a : graph[curr].to)
if(graph[a.first].start == -1){
q.push(a.first);
graph[a.first].start = graph[curr].start;
graph[a.first].depth = graph[curr].depth + 1;
graph[a.first].with = a.second;
}
}
}
int bet;
int find(int u, int N, int M, ll lenght, ll A, ll B){
vector<int> S(M, 1);
S[bet] = 0;
for(int i = 0; i < N; i++)
if(graph[i].start == u && graph[i].with != -1) S[graph[i].with] = 1;
for(int i = 0; i < N; i++)
if(graph[i].start != u && graph[i].with != -1) S[graph[i].with] = 0;
int dist = (ask(S)-lenght*A)/(B-A);
vector<int> poss;
for(int i = 0; i < N; i++)
if(graph[i].start == u && graph[i].depth == dist)
poss.push_back(i);
while(poss.size() > 1){
S.assign(M, 1);
S[bet] = 0;
for(int i = 0; i < N; i++)
if(graph[i].start == u && graph[i].with != -1) S[graph[i].with] = 0;
for(int i = 0; i < N; i++)
if(graph[i].start != u && graph[i].with != -1) S[graph[i].with] = 0;
for(int i = 0; i < poss.size()/2; i++) S[graph[poss[i]].with] = 1;
if(ask(S) == lenght*A){
vector<int> uj;
for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
poss = uj;
}
else poss.resize(poss.size()/2);
}
return poss[0];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
graph.resize(N);
int M = U.size();
for(int i = 0; i < M; i++){
graph[U[i]].to.push_back({V[i],i});
graph[V[i]].to.push_back({U[i],i});
}
vector<int> S(M, 0);
ll dist = ask(S), length = dist/A;
s.resize(M, 0);
int ind = getEdge(0, M, M, dist);
BFS(U[ind], V[ind]);
bet = ind;
answer(find(U[ind], N, M, length, A, B), find(V[ind], N, M, length, A, B));
}
