#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef pair<int,int> pii;
struct node{
vector<pii> to;
int depth = 0, cnt = 0;
bool was = false;
};
vector<node> graph;
void DFS(int curr){
graph[curr].was = true;
for(pii& a : graph[curr].to)
if(!graph[a.first].was)
graph[a.first].depth = graph[curr].depth +1, DFS(a.first);
graph[curr].was = false;
}
int middle = -1;
int cnt(int curr){
graph[curr].was = true;
graph[curr].cnt = 1;
for(pii& a : graph[curr].to)
if(!graph[a.first].was) graph[curr].cnt += cnt(a.first);
graph[curr].was = false;
return graph[curr].cnt;
}
int centroid(int curr, int si){
graph[curr].was = true;
int mxm = si - graph[curr].cnt, ans = -1;
for(pii& a : graph[curr].to)
if(!graph[a.first].was){
mxm = max(mxm, graph[a.first].cnt);
ans = max(ans, centroid(a.first, si));
}
if(mxm <= si/2) ans = curr;
graph[curr].was = false;
return ans;
}
void walk(int curr, vector<pii>& v){
graph[curr].was = true;
for(pii& a : graph[curr].to)
if(!graph[a.first].was){
v.push_back(a);
walk(a.first, v);
}
graph[curr].was = false;
}
vector<int> lef,rig;
int getMiddle(vector<int> v, int at, int A, int B){
if(v.size() <= 2)
return v[0];
int cent = centroid(v[0], cnt(v[0]));
int si = cnt(cent);
int have = 0;
vector<pii> v1, v2;
graph[cent].was = true;
for(pii& a : graph[cent].to){
if(graph[a.first].was) continue;
if(have + graph[a.first].cnt <= si/2)
have += graph[a.first].cnt, v1.push_back(a), walk(a.first, v1);
else
v2.push_back(a), walk(a.first, v2);
}
graph[cent].was = false;
vector<int> S(graph.size()-1, 0);
for(pii& a : v1) S[a.second] = 1;
int d = ask(S);
lef = {cent}, rig = {cent};
for(pii& a : v1) lef.push_back(a.first);
for(pii& a : v2) rig.push_back(a.first);
if(d == at*A){
for(pii& a : v1) graph[a.first].was = true;
return getMiddle(rig, at, A, B);
}
else if(d == at*B){
for(pii& a : v2) graph[a.first].was = true;
return getMiddle(lef, at, A, B);
}
return cent;
}
void walk(int curr, vector<int>& s){
graph[curr].was = true;
for(pii& a : graph[curr].to)
if(!graph[a.first].was)
s[a.second] = 1, walk(a.first, s);
graph[curr].was = false;
}
int get(int root, int N, int at, int A, int B, vector<int> v){
for(node& a : graph) a.was = true, a.depth = -1;
graph[root].depth = 0;
for(int& a : v) graph[a].was = false;
DFS(root);
vector<int> s(N-1, 0);
walk(root, s);
int d = ask(s), depth = (d-at*A)/(B-A);
//cout<<depth<<endl;
vector<pii> poss;
for(int i = 0; i < N; i++)
if(graph[i].depth == depth-1)
for(pii& a : graph[i].to)
if(graph[a.first].depth == depth) poss.push_back(a);
while(poss.size() > 1){
s.assign(N-1, 0);
for(int i = 0; i < poss.size()/2; i++) s[poss[i].second] = 1;
if(ask(s) == (at-1)*A + B) poss.resize(poss.size()/2);
else{
vector<pii> uj;
for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
poss = uj;
}
}
return poss[0].first;
}
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> v(N);
for(int i = 0; i < N; i++) v[i] = i;
vector<int> s(M, 0);
int at = ask(s)/A;
int middle = getMiddle(v, at, A, B);
int S = get(middle, N, at, A, B, lef);
int T = get(middle, N, at, A, B, rig);
answer(S, T);
}
