#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define el '\n'
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define mkp make_pair
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
ll const N = 1e5 + 10;
ll const LOG = 22;
ll const inf = 1e9 + 10;
ll const INF = 1e18 + 10;
ll const mod = 1e9 + 7;
ll const mod2 = 998244353;
ll const K = 400;
ll m;
vector <pii> g[N];
vector <int> w;
ll par[N], idup[N], tin[N], pos[N], used[N];
ll timer = 0, start;
void dfs(ll v, ll p) {
tin[v] = ++timer;
pos[tin[v]] = v;
par[v] = p;
for(auto [u, id] : g[v]) {
if(u != p) {
idup[u] = id;
dfs(u, v);
}
}
}
ll check(ll l, ll r) {
fill(w.begin(), w.end(), 0);
fill(used, used + N, 0);
fr(x, l, r) {
ll v = pos[x];
while(v && !used[v]) {
used[v] = 1;
w[idup[v]] = 1;
v = par[v];
}
}
return ask(w);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m = U.size();
for(int i = 0; i < m; i++) {
g[U[i]].pb({V[i], i});
g[V[i]].pb({U[i], i});
}
w.resize(m);
start = ask(w) / A;
dfs(0, 0);
ll bl = 1, br = N;
while(bl < br) {
ll mid = (bl + br) / 2;
if(check(bl, mid) == start * B)
br = mid;
else
bl = mid + 1;
}
answer(0, pos[bl]);
}
