#include "highway.h"
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ": " << x << "\n";
#define dbgv(x) cerr << #x << ": "; for(const auto &i : x) cerr << i << " "; cerr << "\n";
using namespace std;
using ll = long long;
vector<vector<int>> adj;
vector<pair<long long, long long>> depth;
unordered_map<int, unordered_map<int, int>> path;
int get_path(int node, int i){
return path[node][i];
}
void dfs(int node, int prev){
for(int &i : adj[node]){
if(i == prev) continue;
depth[i] = {depth[node].first + 1, get_path(node, i)};
dfs(i, node);
}
}
int max_depth(int a, int b){
if(depth[a].first > depth[b].first) return a;
return b;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
adj.assign(N, vector<int>());
depth.assign(N, {0, 0});
int ans = 0;
for(int i = 0; i < (int)U.size(); i++){
path[U[i]][V[i]] = i;
path[V[i]][U[i]] = i;
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
vector<int> vec(N - 1, 0);
long long x = ask(vec);
dfs(0, -1);
for(int i = 0; i < (int)depth.size(); i++){
if(depth[i].first == x / (long long)A){
vec[depth[i].second] = 1;
int new_dis = ask(vec);
if(new_dis != x){
ans = max_depth(U[depth[i].second], V[depth[i].second]);
break;
}
}
}
answer(0, ans);
}
