#include "highway.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define ALL(x) begin(x), end(x)
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
// cerr << "start\n";
int M = U.size();
vvii adj(N);
for (int i = 0; i < M; i++) {
adj[U[i]].push_back({V[i], i});
adj[V[i]].push_back({U[i], i});
}
vi vis(N, 0);
vi in_o(N), in_2(N);
int idx = 0, idx2=0;
auto dfs = [&](auto&& self, int p) -> void {
if (vis[p]) return;
vis[p] = 1;
in_o[p] = idx++;
for (auto [o, i] : adj[p]) {
self(self, o);
}
};
auto dfs2 = [&](auto&& self, int p) -> void {
if (vis[p]) return;
vis[p] = 1;
in_2[p] = idx2++;
for (int i_ = adj[p].size()-1; i_ >= 0; i_--) {
auto [o, i] = adj[p][i_];
self(self, o);
}
};
dfs(dfs,0);
vis = vi(N, 0);
dfs2(dfs2,0);
ll og = ask(vi(M, 0));
// for (int i = 0; i < N; i++) cerr << in_o[i] << ' '; cerr << '\n';
// for (int i = 0; i < N; i++) cerr << in_2[i] << ' '; cerr << '\n';
int s, t;
{
int l = 0, h = idx;
while (l < h) {
int m = (l+h)/2;
vi w(M, 0);
for (int i = 0; i < N; i++) {
if (in_o[i] >= m) for (auto [o, j] : adj[i]) w[j] = 1;
}
ll r = ask(w);
if (r > og) l = m+1;
else h = m;
}
for (int i = 0; i < N; i++) if (in_o[i] == l-1) s = i;
}
{
int l = 0, h = idx;
while (l < h) {
int m = (l+h)/2;
vi w(M, 0);
for (int i = 0; i < N; i++) {
if (in_2[i] >= m) for (auto [o, j] : adj[i]) w[j] = 1;
}
ll r = ask(w);
if (r > og) l = m+1;
else h = m;
}
for (int i = 0; i < N; i++) if (in_2[i] == l-1) t = i;
}
// for (int j = 0; j < 50; ++j)
// {
// std::vector<int> w(M);
// for (int i = 0; i < M; ++i)
// {
// w[i] = 0;
// }
// long long toll = ask(w);
// }
// cerr << s << ' ' << t << '\n';
answer(s, t);
}
/*
4 4 1 3 1 3
0 1
0 2
0 3
1 2
5 4 1 3 1 3
0 1
0 2
2 3
2 4
*/
