#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
typedef vector <int> vi;
const int MAXN = 90005;
llint n, m, a, b, L;
int bio[MAXN], pe[MAXN], par[MAXN];
vector <pi> v[MAXN];
///////////////////////////////////////
llint pitaj (vi e) {
vi q(m);
for (auto i : e) q[i] = 1;
return ask(q);
}
int overlap (vi e) {
llint res = pitaj(e);
return (res - L * a) / (b - a);
}
int get_length () {
vector <int> e;
return pitaj(e) / a;
}
///////////////////////////////////////
int dub, R;
vector <int> nodes, edges;
void get_nodes_at_depth (int x, int rod, int curr) {
if (curr == dub) nodes.push_back(x);
par[x] = rod;
for (auto pp : v[x]) {
int sus = pp.first, ind = pp.second;
if (sus == rod) {
pe[x] = ind;
continue;
}
get_nodes_at_depth(sus, x, curr + 1);
}
}
void climb (int x) {
while (1) {
if (bio[x]) break;
bio[x] = 1;
if (x == R) break;
edges.push_back(pe[x]);
x = par[x];
}
}
int find_node (vi curr) {
if (curr.size() == 1) return curr[0];
int siz = curr.size();
vi lo, hi;
for (int i = 0; i < siz; i++) {
if (i * 2 < siz) lo.push_back(curr[i]); else hi.push_back(curr[i]);
}
edges.clear();
memset(bio, 0, sizeof bio);
for (auto x : lo) climb(x);
if (overlap(edges) == dub) return find_node(lo);
return find_node(hi);
}
int solve_subtree (int root, int rod, int len) {
nodes.clear(); dub = len; R = root;
get_nodes_at_depth(root, rod, 0);
return find_node(nodes);
}
void find_pair (int N, vi U, vi V, int A, int B) {
n = N; m = U.size(), a = A, b = B;
for (int i = 0; i < m; i++) {
v[U[i]].push_back({V[i], i});
v[V[i]].push_back({U[i], i});
}
L = get_length();
answer(0, solve_subtree(0, -1, L));
}
