#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void dfs(int node, int parent, vector<vector<int>> adj, vector<int>& depths){
for(int v : adj[node]){
if(v == parent) return;
depths[v] = depths[node] + 1;
dfs(v, node, adj, depths);
}
}
pair<int, int> search(int N, vector<int> U, vector<int> V, int A, int B){
int M = U.size();
vector<int> initial(M, 0);
ll initialCost = ask(initial);
int distance = initialCost / A;
vector<vector<int>> adj;
for(int i = 0; i < M; i++){
int u = U[i]; int v = V[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> depths(M);
dfs(0, 0, adj, depths);
int secondLocation = 0;
for(int i = 0; i < N; i++){
if(depths[i] == distance){
initial[i] = 1;
ll thisPrice = ask(initial);
if(thisPrice - B + A == initialCost) return {0, secondLocation};
}
}
return {0, secondLocation};
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
pair<int, int> ans = search(N, U, V, A, B);
answer(ans.first, ans.second);
// int A_; cin >> A_;
}
// #include "grader.cpp"
// #include "grader.cpp"
