#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
vector<vector<int>> graph;
int normal;
map<pair<int, int>, int> edgeToIndex;
int bsEdges(int M) {
int l=0; int r = M-1;
while (l<r) {
vector<int> a(M, 0);
int m = (l + r) / 2;
for (int i=l; i<=m; i++) {
a[i] = 1;
}
if (ask(a) != normal) {
r = m;
}
else {
l = m+1;
}
}
return l;
}
vector<int> side;
vector<bool> visited;
void sideDFS(int v) {
if (visited[v]) return;
visited[v] = 1;
side[v] = 1;
for (int i: graph[v]) {
sideDFS(i);
}
}
vector<pair<int, int>> cand;
void findLevel(int v, int t, int l, int p) {
if (visited[v]) return;
visited[v] = 1;
if (l == t) {
cand.push_back({v, p});
}
for (int i: graph[v]) {
findLevel(i, t, l+1, v);
}
}
int BS2(vector<pair<int, int>> edges, int M) {
int l = 0; int r = edges.size()-1;
while (l<r) {
vector<int> a(M, 0);
int m = (l + r) / 2;
for (int i=l; i<=m; i++) {
a[edgeToIndex[{min(edges[i].first, edges[i].second), max(edges[i].first, edges[i].second)}]] = 1;
}
if (ask(a) != normal) {
r = m;
}
else {
l = m+1;
}
}
return edges[l].first;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
int M = U.size();
assert(M == N-1);
vector<int> a(M, 0);
normal = ask(a);
vector<pair<int, int>> edges;
graph.assign(N, vector<int>());
edgeToIndex.clear();
for (int i=0; i<M; i++) {
edges.push_back({min(U[i], V[i]), max(U[i], V[i])});
graph[U[i]].push_back(V[i]);
graph[V[i]].push_back(U[i]);
edgeToIndex[{min(U[i], V[i]), max(U[i], V[i])}] = i;
}
pair<int, int> edgeOnPath = edges[bsEdges(M)];
side.assign(N, 0);
visited.assign(N, 0);
visited[edgeOnPath.second] = 1;
sideDFS(edgeOnPath.first);
pair<int, int> length;
{
vector<int> askk(M, 0);
for (int i=0; i<M; i++) {
if (side[edges[i].first] && side[edges[i].second]) askk[i] = 1;
}
int tmp = ask(askk);
length.first = ((tmp-normal)/(B-A));
length.second = (normal - (length.first * A)) / A -1;
}
visited.assign(N, 0);
cand.clear();
visited[edgeOnPath.second] = 1;
findLevel(edgeOnPath.first, length.first, 0, -1);
int start = BS2(cand, M);
visited.assign(N, 0);
cand.clear();
visited[edgeOnPath.first] = 1;
findLevel(edgeOnPath.second, length.second, 0, -1);
int end = BS2(cand, M);
answer(min(start, end), max(start, end));
}
