#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 3e2;
vector<int> edges;
vector<pair<int, int>> g[MAXN];
void dfs(int v, int p){
for (auto e : g[v]){
int u = e.first, i = e.second;
if (u != p){
edges.push_back(i);
dfs(u, v);
}
}
}
vector<pair<int, int>> vec;
int dep;
void dfs2(int v, int p, int d){
for (auto e : g[v]){
int u = e.first, i = e.second;
if (u != p){
if (d + 1 == dep) vec.emplace_back(i, u);
dfs2(u, v, d + 1);
}
}
}
int N, M;
vector<int> U, V;
bool different_groups(vector<int> &grp){
vector<int> w(M);
for (int i = 0; i < M; i++){
w[i] = grp[U[i]] == grp[V[i]];
}
return ask(w) % 2 == 1;
}
void find_pair(int _N, vector<int> _U, vector<int> _V, int A, int B) {
N = _N, U = _U, V = _V, M = U.size();
for (int i = 0; i < M; i++){
g[U[i]].emplace_back(V[i], i);
g[V[i]].emplace_back(U[i], i);
}
if (A == 1 && B == 2){
vector<int> grp(N, 0);
for (int j = 0; j < 17; j++){
for (int i = 0; i < N; i++){
grp[i] = (i & (1 << j)) ? 1 : 0;
}
if (different_groups(grp)) break;
}
vector<int> q, p;
for (int i = 0; i < N; i++){
if (grp[i]) q.push_back(i); else
p.push_back(i);
}
int S = -1, T = -1;
int l = 0, r = q.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(grp), 0);
for (int i = 0; i <= mid; i++) grp[q[i]] = 1;
if (different_groups(grp)){
S = q[mid];
r = mid - 1;
} else l = mid + 1;
}
l = 0, r = p.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(grp), 0);
for (int i = 0; i <= mid; i++) grp[p[i]] = 1;
if (different_groups(grp)){
T = p[mid];
r = mid - 1;
} else l = mid + 1;
}
answer(S, T);
return;
}
dfs(0, 0);
vector<int> w(M, 0);
ll onlyA = ask(w);
int ind = 0;
int l = 0, r = M - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 0);
for (int i = 0; i <= mid; i++) w[edges[i]] = 1;
ll res = ask(w);
if (res != onlyA){
ind = edges[mid];
r = mid - 1;
} else l = mid + 1;
}
for (int i = 0; i < g[U[ind]].size(); i++){
if (g[U[ind]][i].first == V[ind]) g[U[ind]].erase(g[U[ind]].begin() + i);
}
for (int i = 0; i < g[V[ind]].size(); i++){
if (g[V[ind]][i].first == U[ind]) g[V[ind]].erase(g[V[ind]].begin() + i);
}
if (g[U[ind]].empty() && g[V[ind]].empty()){
answer(U[ind], V[ind]);
return;
}
int S = -1, T = -1;
edges.clear();
dfs(U[ind], U[ind]);
fill(all(w), 0);
for (int i : edges) w[i] = 1;
ll res = ask(w);
dep = (res - onlyA) / (B - A);
if (dep != 0) {
dfs2(U[ind], U[ind], 0);
l = 0, r = vec.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 0);
for (int i = 0; i <= mid; i++) w[vec[i].first] = 1;
res = ask(w);
if (res != onlyA){
S = vec[mid].second;
r = mid - 1;
} else l = mid + 1;
}
} else S = U[ind];
edges.clear();
dfs(V[ind], V[ind]);
fill(all(w), 0);
for (int i : edges) w[i] = 1;
res = ask(w);
dep = (res - onlyA) / (B - A);
if (dep != 0) {
vec.clear();
dfs2(V[ind], V[ind], 0);
l = 0, r = vec.size() - 1;
while (l <= r){
int mid = (l + r) >> 1;
fill(all(w), 0);
for (int i = 0; i <= mid; i++) w[vec[i].first] = 1;
res = ask(w);
if (res != onlyA){
T = vec[mid].second;
r = mid - 1;
} else l = mid + 1;
}
} else T = V[ind];
answer(S, T);
}
