#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define isz(a) ((signed)a.size())
using ll = long long;
struct edge_t{
int u, v;
};
const int N = 90'000 + 5, M = 130'000 + 5, LN = 17;
int n, m;
int a, b;
vector <edge_t> edge;
vector <int> adj[N];
vector <int> vquery;
namespace subtask1234{
bool check(){
return m == n - 1;
}
int length_path;
int pv[N];
int pe[N];
int ctrtour, tour[N];
void dfs_tour(int u){
tour[ctrtour] = u;
ctrtour++;
for (auto i: adj[u]){
if (i == pe[u]){
continue;
}
auto v = u ^ edge[i].u ^ edge[i].v;
pv[v] = u;
pe[v] = i;
dfs_tour(v);
}
}
int solve_fixed(int s){
pv[s] = -1;
pe[s] = -1;
ctrtour = 0;
dfs_tour(s);
int lo = 1, hi = n - 1;
while (lo < hi){
int mid = (lo + hi) >> 1;
fill(vquery.begin(), vquery.end(), 0);
for (int pos = 1; pos <= mid; pos++){
vquery[pe[tour[pos]]] = 1;
}
if (ask(vquery) == (ll)length_path * b){
hi = mid;
}
else{
lo = mid + 1;
}
}
return tour[lo];
}
int depth[N];
void dfs_depth(int u){
for (auto i: adj[u]){
if (i == pe[u]){
continue;
}
int v = u ^ edge[i].u ^ edge[i].v;
pv[v] = u;
pe[v] = i;
depth[v] = depth[u] + 1;
dfs_depth(v);
}
}
int find_one(){
int root = 1;
pv[root] = -1;
pe[root] = -1;
depth[root] = 0;
dfs_depth(root);
int lo = 1, hi = *max_element(depth, depth + n);
while (lo < hi){
int mid = (lo + hi + 1) >> 1;
fill(vquery.begin(), vquery.end(), 0);
for (int u = 0; u < n; u++){
if (depth[u] >= mid){
vquery[pe[u]] = 1;
}
}
if (ask(vquery) == (ll)length_path * a){
hi = mid - 1;
}
else{
lo = mid;
}
}
vector <int> layer;
for (int u = 0; u < n; u++){
if (depth[u] == lo){
layer.emplace_back(u);
}
}
lo = 0; hi = isz(layer) - 1;
while (lo < hi){
int mid = (lo + hi) >> 1;
fill(vquery.begin(), vquery.end(), 0);
for (int i = 0; i <= mid; i++){
vquery[pe[layer[i]]] = 1;
}
if (ask(vquery) == (ll)length_path * a){
lo = mid + 1;
}
else{
hi = mid;
}
}
return layer[lo];
}
void solve(){
fill(vquery.begin(), vquery.end(), 0);
length_path = ask(vquery) / a;
int s = find_one();
int t = solve_fixed(s);
answer(s, t);
}
}
namespace subtask5{
bool check(){
return a == 1 and b == 2;
}
int odd_weight;
int even_weight;
int color[N];
bool same_color(){
for (int i = 0; i < m; i++){
auto &[u, v] = edge[i];
vquery[i] = (color[u] == color[v] ? even_weight : odd_weight);
}
return (ask(vquery) % 2 == 0 ? true : false);
}
bool same[LN];
void solve(){
odd_weight = (a % 2 != 0 ? 0 : 1);
even_weight = 1 - odd_weight;
for (int bit = 0; bit < LN; bit++){
for (int u = 0; u < n; u++){
color[u] = u >> bit & 1;
}
same[bit] = same_color();
}
int s = -1, t = -1;
for (int bit = 0; bit < LN; bit++){
if (same[bit]){
continue;
}
vector <int> cpn;
for (int u = 0; u < n; u++){
if (u >> bit & 1){
cpn.emplace_back(u);
}
}
while (isz(cpn) != 1){
vector <int> cpn1, cpn2;
for (auto u: cpn){
if (isz(cpn1) <= isz(cpn2)){
cpn1.emplace_back(u);
}
else{
cpn2.emplace_back(u);
}
}
fill(color, color + n, 0);
for (auto u: cpn1){
color[u] = 1;
}
if (not same_color()){
cpn = cpn1;
}
else{
cpn = cpn2;
}
}
s = cpn.back();
break;
}
t = s;
for (int bit = 0; bit < LN; bit++){
if (not same[bit]){
t ^= (1 << bit);
}
}
answer(s, t);
}
}
void find_pair(int _n, vector <int> _u, vector <int> _v, int _a, int _b){
n = _n;
m = isz(_u);
edge.resize(m);
for (int i = 0; i < m; i++){
int u = _u[i], v = _v[i];
edge[i] = edge_t{u, v};
adj[u].emplace_back(i);
adj[v].emplace_back(i);
}
a = _a;
b = _b;
vquery.resize(m);
// if (subtask1234::check()){
// subtask1234::solve();
// return;
// }
if (subtask5::check()){
subtask5::solve();
return;
}
}
