#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define mkp make_pair
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}
int dis[maxn];
vi col;
vector<pii> E[maxn],v;
void st(int nd,int pr){
if(nd) dis[nd]=dis[pr]+1;
v.pb({dis[nd],nd});
for(auto i : E[nd]){
if(i.ff != pr){
st(i.ff,nd);
}
}
}
bool dfs(int nd,int pr,int pos){
if(nd==pos) return 1;
for(auto i : E[nd]){
if(i.ff != pr){
if(dfs(i.ff,nd,pos)){
col[i.ss]=1;
return 1;
}
else col[i.ss]=0;
}
}
return 0;
}
void find_pair(int N, vi U, vi V, int A, int B) {
int M = sz(U);
// if(M != N-1){
// answer(rand()%N,rand()%N);
// return;
// }
for(int i = 0;i < M;i++){
E[U[i]].pb({V[i],i});
E[V[i]].pb({U[i],i});
}
col.resize(M);
int ans = 0;
st(0,-1);
sort(all(v));
for(int i = 0;i < sz(v);i++){
for(int j = 0;j < sz(col);j++) col[j]=0;
dfs(0,-1,v[i].ss);
if(ask(col) == v[i].ff*B) ans=i;
}
// cout<<ans<<'\n';
answer(0, ans);
}
