#include "highway.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<pair<int,int>> adj[N];
int par[N];
int paredge[N];
int dep[N];
vector<int> w;
void dfs(int v,int pr,int edge){
//cout << v << " " << pr << " " << edge << endl;
par[v] = pr;
paredge[v] = edge;
for(auto u:adj[v]){
if(u.first == pr)continue;
dep[u.first] = dep[v] + 1;
dfs(u.first,v,u.second);
}
}
void dfs2(int v,int pr){
w[paredge[v]] = 1;
for(auto u:adj[v]){
if(u.first == pr)continue;
dfs2(u.first,v);
}
}
vector<int> xx;
void dfs3(int v,int pr,int target){
if(dep[v] == target)
xx.push_back(v);
for(auto u:adj[v]){
if(u.first == pr)continue;
dfs3(u.first,v,target);
}
}
int group[N];
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
int m = u.size();
for(int i = 0;i<m;i++){
adj[u[i]].push_back({v[i],i});
adj[v[i]].push_back({u[i],i});
}
w.assign(m,0);
if(a == 1 && b == 2){
//solution with making sure s on first group t on second group
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> x;
for(int i = 0;i<n;i++){
x.push_back(i);
}
while(1){
shuffle(x.begin(),x.end(),rng);
int mid = (n-1) / 2;
w.assign(m,0);
for(int i = 0;i<=mid;i++){
group[x[i]] = 0;
}
for(int i = mid+1;i<n;i++){
group[x[i]] = 1;
}
for(int i = 0;i<m;i++){
if(group[u[i]] == group[v[i]]){
w[i] = 1;
}
}
if(ask(w) & 1){
break;
}
}
int s = -1,t = -1;
int ll = 0,rr = (n-1)/2;
while(ll < rr){
int mid = (ll + rr)/2;
w.assign(m,0);
for(int i = 0;i<=mid;i++){
group[x[i]] = 0;
}
for(int i = mid+1;i<n;i++){
group[x[i]] = 1;
}
for(int i = 0;i<m;i++){
if(group[u[i]] == group[v[i]]){
w[i] = 1;
}
}
if(ask(w) & 1){
rr = mid;
}
else ll = mid+1;
}
s = x[ll];
ll = (n-1)/2 + 1,rr = n-1;
while(ll < rr){
int mid = (ll + rr)/2;
w.assign(m,0);
for(int i = 0;i<=mid;i++){
group[x[i]] = 0;
}
for(int i = mid+1;i<n;i++){
group[x[i]] = 1;
}
for(int i = 0;i<m;i++){
if(group[u[i]] == group[v[i]]){
w[i] = 1;
}
}
if(ask(w) & 1){
ll = mid + 1;
}
else rr = mid;
}
t = x[ll];
answer(s,t);
//solution with finding xor of s and t
/*
int s = 0;
int xr = 0;
int least = -1;
for(int i = 0;(1<<i)<n;i++){
w.assign(m,0);
for(int j = 0;j<m;j++){
int nowmask = (1<<i);
if( ((u[j] & nowmask) == nowmask) == ((v[j] & nowmask) == nowmask)){
w[j] = 1;
}
}
if(ask(w) & 1){
if(least == -1){
least = i;
s = (1<<least);
}
xr += (1<<i);
}
}
assert(least != -1);
for(int i = 0;(1<<i)<n;i++){
if(i == least)continue;
w.assign(m,0);
for(int j = 0;j<m;j++){
int nowmask = (1<<i) + (1<<least);
if( ((u[j] & nowmask) == nowmask) == ((v[j] & nowmask) == nowmask)){
w[j] = 1;
}
}
if(ask(w) & 1){
s += (1<<i);
}
}
answer(s,xr^s);*/
return;
}
long long len = ask(w) / a;
vector<int> x;
for(int i = 0;i<m;i++){
x.push_back(i);
}
while(x.size() > 1){
vector<int> tmp;
while(tmp.size() < x.size()){
tmp.push_back(x.back());
x.pop_back();
}
w.assign(m,0);
for(auto u:tmp){
w[u] = 1;
}
if(ask(w) != len * a){
x = tmp;
}
}
int root = u[x[0]];
//cout << root << endl;
dfs(root,-1,-1);
w.assign(m,0);
dfs2(v[x[0]],root);
int dep1 = (ask(w) - len*a) / (b-a);
int dep2 = len - dep1;
int s = -1,t = -1;
if(dep1 == 0)s = root;
if(dep2 == 0)t = root;
//cout << dep1 << " " << dep2 << endl;
if(s == -1){
xx.clear();
dfs3(v[x[0]],root,dep1);
while(xx.size() > 1){
vector<int> tmp;
while(tmp.size() < xx.size()){
tmp.push_back(xx.back());
xx.pop_back();
}
w.assign(m,0);
for(auto u:tmp){
w[paredge[u]] = 1;
}
if(ask(w) != len * a){
xx = tmp;
}
}
s = xx[0];
}
if(t == -1){
xx.clear();
for(auto u:adj[root]){
if(u.first == v[x[0]])continue;
dfs3(u.first,root,dep2);
}
while(xx.size() > 1){
vector<int> tmp;
while(tmp.size() < xx.size()){
tmp.push_back(xx.back());
xx.pop_back();
}
w.assign(m,0);
for(auto u:tmp){
w[paredge[u]] = 1;
}
if(ask(w) != len * a){
xx = tmp;
}
}
t = xx[0];
}
answer(s,t);
}
