#include<iostream>
#include<vector>
#include "highway.h"
#define f first
#define s second
#define DIM 130005
using namespace std;
static int t[DIM], p[DIM], nr, ok[DIM];
static pair<int, int> w[DIM];
static vector<int> r, v[DIM];
static void dfs(int nod, int tt){
t[nod] = tt;
int i, vecin;
for(i = 0; i < v[nod].size(); i++){
vecin = v[nod][i];
if(vecin != tt){
p[vecin] = ++nr;
}
}
for(i = 0; i < v[nod].size(); i++){
vecin = v[nod][i];
if(vecin != tt){
dfs(vecin, nod);
}
}
}
static void dfs2(int nod, int tt, int niv, int num){
if(niv != 0 && ok[nod] == 1){
return;
}
if(niv == num){
p[nod] = ++nr;
}
else{
for(int i = 0; i < v[nod].size(); i++){
if(v[nod][i] != tt){
dfs2(v[nod][i], nod, niv + 1, num);
}
}
}
}
void find_pair(int n, vector<int> U, vector<int> V, int a, int b){
int m, i, st, dr, mid, num, niv, x, y, nod;
long long sum, cost;
m = U.size();
r.resize(m);
for(i = 0; i < m; i++){
w[i] = make_pair(U[i] + 1, V[i] + 1);
v[ w[i].f ].push_back(w[i].s);
v[ w[i].s ].push_back(w[i].f);
}
dfs(1, 0);
for(i = 0; i < m; i++){
if(t[ w[i].s ] == w[i].f){
swap(w[i].f, w[i].s);
}
r[i] = 0;
}
sum = ask(r);
st = 1;
dr = n - 1;
while(st < dr){
mid = (st + dr) / 2;
for(i = 0; i < m; i++){
if(p[ w[i].f ] > mid && p[ w[i].f ] <= dr){
r[i] = 1;
}
else{
r[i] = 0;
}
}
if(ask(r) > sum){
st = mid + 1;
}
else{
dr = mid;
}
}
for(i = 2; i <= n; i++){
if(p[i] == st){
x = i;
}
}
num = sum / a;
for(i = x; i != 0; i = t[i]){
p[i] = -1;
ok[i] = 1;
}
for(i = 0; i < m; i++){
if(p[ w[i].f ] == -1){
r[i] = 1;
}
else{
r[i] = 0;
}
}
cost = ask(r);
niv = (cost - sum) / (b - a);
num -= niv;
for(i = x; niv > 0; i = t[i], niv--);
nod = i;
if(num == 0){
answer(nod - 1, x - 1);
return;
}
for(i = 1; i <= n; i++){
p[i] = 0;
}
nr = 0;
dfs2(nod, t[nod], 0, num);
p[x] = 0;
st = 1;
dr = nr;
while(st < dr){
mid = (st + dr) / 2;
for(i = 0; i < m; i++){
if(p[ w[i].f ] > mid && p[ w[i].f ] <= dr){
r[i] = 1;
}
else{
r[i] = 0;
}
}
if(ask(r) > sum){
st = mid + 1;
}
else{
dr = mid;
}
}
for(i = 2; i <= n; i++){
if(p[i] == st){
y = i;
}
}
answer(x - 1, y - 1);
}
