#include "highway.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
ll m, n, a, b, largo;
vector<int>adj[100000];
vector<int>idx[100000];
int keepBanned;
void llenar(int dd, int ht, int v, vector<int>&w){
for(int i = dd ; i <= ht ; i ++)w[i] = v;
}
void find_edje(int &ejeMedio, vector<int>&w){
int li = 0, ls = m-1, pos;
pos = (li + ls)/2;
ll tried[130003];
for(int i = 0 ; i < m ; i ++)tried[i] = -1;
while(li + 1 < ls){
llenar(0, m-1, 0, w);
llenar(0, keepBanned-1, 1, w);
llenar(0, pos, 1, w);
ll res = ask(w);
tried[pos] = res;
if(res > largo*a){
ls = pos;
}else{
li = pos + 1;
}
pos = (li + ls ) / 2 ;
}
if(tried[li] == -1){
llenar(0, m-1, 0, w);
llenar(0, pos, 1, w);
tried[li] = ask(w);
}
if(tried[li] > largo*a){
ejeMedio = li;
}else ejeMedio = ls;
}
vector<int>getEdjes(int dd, int other, int ban, vector<int>&dist, vector<int>&nodes){
queue<int>cola;
dist.clear();
nodes.clear();
vector<int>ans;
for(int i = 0 ; i < n ; i ++)dist.pb(INT_MAX);
cola.push(other);
cola.push(dd);
dist[dd] = 0;
bool vis[n+1];
bool search[n+1];
bool banned[m+1];
memset(vis, false, sizeof vis);
memset(search, false, sizeof search);
memset(banned, false, sizeof banned);
banned[ban] = true;
vis[dd] = true;
vis[other] = true;
search[dd] = true;
while(!cola.empty()){
int cur = cola.front();
cola.pop();
for(int i = 0 ; i < adj[cur].size() ; i ++){
if(banned[idx[cur][i]] or idx[cur][i] < keepBanned)continue;
if(vis[adj[cur][i]])continue;
vis[adj[cur][i]] = true;
if(search[cur]){
search[adj[cur][i]] = true;
dist[adj[cur][i]] = dist[cur] + 1;
cola.push(adj[cur][i]);
ans.pb(idx[cur][i]);
nodes.pb(adj[cur][i]);
}else{
cola.push(adj[cur][i]);
}
}
}
return ans;
}
int cualAfecta(vector<int>&nodos, vector<int>&ejes, vector<int>&w){
int li = 0, ls = ejes.size()-1;
int pos = (li + ls)/2;
while(li + 1 < ls){
llenar(0, m-1, 0, w);
llenar(0, keepBanned -1 , 1, w);
for(int i = li ; i <= pos ; i ++)w[ejes[i]] = 1;
if(ask(w) > largo*a){
ls = pos;
}else{
li = pos + 1;
}
pos = (li + ls)/2;
}
if(li == ls)return nodos[li];
llenar(0, m-1, 0, w);
w[ejes[li]] = 1;
if(ask(w) > largo * a)return nodos[li];
else return nodos[ls];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
n = N;
m = U.size();
a = A;
b = B;
vector<int>w;
for(int i = 0 ; i < m ; i ++){
adj[U[i]].pb(V[i]);
adj[V[i]].pb(U[i]);
idx[U[i]].pb(i);
idx[V[i]].pb(i);
w.pb(0);
}
largo = ask(w)/a;
int ejeMedio;
find_edje(ejeMedio, w);
keepBanned = ejeMedio;
//cout << ejeMedio << endl;
//cout << U[ejeMedio] << " " << V[ejeMedio] << endl;
vector<int>distancias, nodos, ejes;
ejes = getEdjes(V[ejeMedio], U[ejeMedio], ejeMedio, distancias, nodos);
llenar(0, m-1, 0, w);
llenar(0, keepBanned-1, 1, w);
for(auto i : ejes)w[i] = 1;
ll distkt = (ask(w)-largo*a)/(b-a);
//cout << "dist " << V[ejeMedio] << " = " << distkt << endl;
int s, t;
if(distkt == 0){
t = V[ejeMedio];
}else{
vector<int>tempNodos, tempEje;
for(int i = 0 ; i < nodos.size() ; i ++){
if(distancias[nodos[i]] == distkt){
tempNodos.pb(nodos[i]);
tempEje.pb(ejes[i]);
}
}
//cout << " opciones " ;
//for(auto i : tempNodos)cout << i << " " ;
//cout << endl;
t = cualAfecta(tempNodos, tempEje, w);
}
ejes = getEdjes(U[ejeMedio], V[ejeMedio], ejeMedio, distancias, nodos);
llenar(0, m-1, 0, w);
llenar(0, keepBanned-1, 1, w);
for(auto i : ejes)w[i] = 1;
distkt = (ask(w)-largo*a)/(b-a);
//cout << "dist " << U[ejeMedio] << " = " << distkt << endl;
if(distkt == 0){
s = U[ejeMedio];
}else{
vector<int>tempNodos, tempEje;
for(int i = 0 ; i < nodos.size() ; i ++){
if(distancias[nodos[i]] == distkt){
tempNodos.pb(nodos[i]);
tempEje.pb(ejes[i]);
}
}
s = cualAfecta(tempNodos, tempEje, w);
}
//cout << s << " " << t << endl;
answer(s, t);
}
