#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
//~ ll ask(vector<int> w);
//~ void answer(int s, int t);
void DFS(int x, vector<vector<pair<int, int>>>& adj, vector<pair<int, int>>& pr, vector<vector<int>>& depth, int p, int edge, int d){
pr[x] = {p, edge};
depth[d].push_back(x);
for(pair<int, int> pr2 : adj[x]){
int node = pr2.first;
int e = pr2.second;
if(node != p) DFS(node, adj, pr, depth, x, e, d + 1);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
int n = N;
int m = (int)U.size();
if(m != n - 1) {answer(0, 1); return;}
vector<vector<pair<int, int>>> adj(n);
for(int i = 0; i < m; i++){
int a = U[i]; int b = V[i];
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
vector<pair<int, int>> p(n);
vector<vector<int>> depth(n);
DFS(0, adj, p, depth, -1, -1, 0);
vector<int> w(m, 0);
ll dist = ask(w) / A;
//Now I want to find the depth of the lowest node in the tree.
int lo = 0;
int hi = n-1;
int bst;
while(lo <= hi){
int mid = (lo + hi) / 2;
w.assign(m, 0);
for(int i = 0; i <= mid; i++){
for(int x : depth[i]){
if(x == 0) continue;
w[p[x].second] = 1;
}
}
ll d = ask(w);
if(d == dist * B){
bst = mid;
hi = mid - 1;
}else lo = mid + 1;
}
lo = 0;
hi = (int)depth[bst].size() - 1;
int s;
while(lo <= hi){
int mid = (lo + hi) / 2;
w.assign(m, 0);
for(int i = lo; i <= mid; i++){
int x = depth[bst][i];
if(x == 0) continue;
w[p[x].second] = 1;
}
ll d = ask(w);
if(d != dist * A){
s = depth[bst][mid];
hi = mid - 1;
}else lo = mid + 1;
}
w.assign(m, 0);
int curr_node = s;
while(p[curr_node].second != -1){
w[p[curr_node].second] = 1;
curr_node = p[curr_node].first;
}
ll dist2 = ask(w);
ll depth_anc = bst - ((dist2 - dist * A) / (B-A));
ll bst2 = dist - bst + 2 * depth_anc;
if(bst - bst2 == dist){
int curr_node = s;
int curr_depth = bst;
while(curr_node != -1){
if(curr_depth == bst2){
answer(s, curr_node); return;
}
curr_node = p[curr_node].first;
curr_depth--;
}
}
lo = 0;
hi = (int)depth[bst2].size() - 1;
int t;
while(lo <= hi){
int mid = (lo + hi) / 2;
vector<int> added;
for(int i = lo; i <= mid; i++){
int x = depth[bst2][i];
if(x == 0 || w[p[x].second] == 1) continue;
w[p[x].second] = 1;
added.push_back(p[x].second);
}
ll d = ask(w);
if(d != dist2){
t = depth[bst2][mid];
hi = mid - 1;
}else lo = mid + 1;
for(int x : added) w[x] = 0;
}
answer(s, t);
return;
}
//~ namespace {
//~ constexpr int MAX_NUM_CALLS = 100;
//~ constexpr long long INF = 1LL << 61;
//~ int N, M, A, B, S, T;
//~ std::vector<int> U, V;
//~ std::vector<std::vector<std::pair<int, int>>> graph;
//~ bool answered, wrong_pair;
//~ int num_calls;
//~ int read_int() {
//~ int x;
//~ if (scanf("%d", &x) != 1) {
//~ fprintf(stderr, "Error while reading input\n");
//~ exit(1);
//~ }
//~ return x;
//~ }
//~ void wrong_answer(const char *MSG) {
//~ printf("Wrong Answer: %s\n", MSG);
//~ exit(0);
//~ }
//~ } // namespace
//~ long long ask(const std::vector<int> &w) {
//~ if (++num_calls > MAX_NUM_CALLS) {
//~ wrong_answer("more than 100 calls to ask");
//~ }
//~ if (w.size() != (size_t)M) {
//~ wrong_answer("w is invalid");
//~ }
//~ for (size_t i = 0; i < w.size(); ++i) {
//~ if (!(w[i] == 0 || w[i] == 1)) {
//~ wrong_answer("w is invalid");
//~ }
//~ }
//~ std::vector<bool> visited(N, false);
//~ std::vector<long long> current_dist(N, INF);
//~ std::queue<int> qa, qb;
//~ qa.push(S);
//~ current_dist[S] = 0;
//~ while (!qa.empty() || !qb.empty()) {
//~ int v;
//~ if (qb.empty() ||
//~ (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
//~ v = qa.front();
//~ qa.pop();
//~ } else {
//~ v = qb.front();
//~ qb.pop();
//~ }
//~ if (visited[v]) {
//~ continue;
//~ }
//~ visited[v] = true;
//~ long long d = current_dist[v];
//~ if (v == T) {
//~ return d;
//~ }
//~ for (auto e : graph[v]) {
//~ int vv = e.first;
//~ int ei = e.second;
//~ if (!visited[vv]) {
//~ if (w[ei] == 0) {
//~ if (current_dist[vv] > d + A) {
//~ current_dist[vv] = d + A;
//~ qa.push(vv);
//~ }
//~ } else {
//~ if (current_dist[vv] > d + B) {
//~ current_dist[vv] = d + B;
//~ qb.push(vv);
//~ }
//~ }
//~ }
//~ }
//~ }
//~ return -1;
//~ }
//~ void answer(int s, int t) {
//~ if (answered) {
//~ wrong_answer("answered not exactly once");
//~ }
//~ if (!((s == S && t == T) || (s == T && t == S))) {
//~ wrong_pair = true;
//~ }
//~ answered = true;
//~ }
//~ int main() {
//~ N = read_int();
//~ M = read_int();
//~ A = read_int();
//~ B = read_int();
//~ S = read_int();
//~ T = read_int();
//~ U.resize(M);
//~ V.resize(M);
//~ graph.assign(N, std::vector<std::pair<int, int>>());
//~ for (int i = 0; i < M; ++i) {
//~ U[i] = read_int();
//~ V[i] = read_int();
//~ graph[U[i]].push_back({V[i], i});
//~ graph[V[i]].push_back({U[i], i});
//~ }
//~ answered = false;
//~ wrong_pair = false;
//~ num_calls = 0;
//~ find_pair(N, U, V, A, B);
//~ if (!answered) {
//~ wrong_answer("answered not exactly once");
//~ }
//~ if (wrong_pair) {
//~ wrong_answer("{s, t} is wrong");
//~ }
//~ printf("Accepted: %d\n", num_calls);
//~ return 0;
//~ }
