#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> ii;
const int mxN = 90005;
const int mxM = 130005;
int N, M, A, B;
int E[mxM];
vector<int> al[mxN], num;
vector<ii> pa;
vector<int> w;
ll L;
int qcnt = 0;
bool query() {
++qcnt;
assert(qcnt <= 100);
ll r = ask(w);
//cout << qcnt << " :: ";
//FOR(i,0,M-1) cout << w[i] << ' ';
//cout << " :: " << r << endl;
return r == L;
}
void bfs(vector<int> s) {
int cnt = 0;
num.assign(N,-1);
pa.assign(N,ii(-1,-1));
queue<int> q;
for (auto& u : s) { num[u] = cnt++, pa[u].second = u, q.push(u); }
while (!q.empty()) {
int u = q.front(); q.pop();
for (int e : al[u]) {
int v = E[e]^u;
if (num[v] == -1) { num[v] = cnt++, pa[v] = ii(e,pa[u].second), q.push(v); }
}
}
}
void setW(vector<int>::iterator s, vector<int>::iterator e, int p) {
vector<int> vis(N,0);
for (auto it = s; it != e; ++it) {
for (int x = *it; pa[x].first != -1 && !vis[x]; x = E[pa[x].first]^x) {
vis[x] = 1;
w[pa[x].first] = p;
}
}
}
int solve(int s) {
vector<int> vtx;
FOR(i,0,N-1) if (pa[i].second == s) vtx.push_back(i);
sort(ALL(vtx),[](int a, int b) { return num[a] < num[b]; });
//cout << "VTX: ";
//for (auto& x : vtx) cout << x << ' ';
//cout << endl;
setW(ALL(vtx),1);
int lo = -1, hi = SZ(vtx)-1;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
setW(vtx.begin(),vtx.begin()+mid+1,0);
if (query()) hi = mid;
else lo = mid;
setW(vtx.begin(),vtx.begin()+mid+1,1);
}
setW(ALL(vtx),0);
//TRACE(hi _ vtx[hi]);
return vtx[hi];
}
void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
N = _N;
M = U.size();
FOR(i,0,M-1){
E[i] = U[i]^V[i];
al[U[i]].push_back(i);
al[V[i]].push_back(i);
}
A = _A, B = _B;
w.assign(M,0);
L = ask(w);
int lo = -1, hi = M;
while (hi-lo > 1) {
int mid = (lo+hi)/2;
FOR(i,lo+1,mid) w[i] = 1;
if (query()) lo = mid;
else {
FOR(i,lo+1,mid) w[i] = 0;
hi = mid;
}
}
bfs({U[hi],V[hi]});
w.assign(M,1);
vector<int> vtx(N); iota(ALL(vtx),0);
setW(ALL(vtx),0);
w[hi] = 0;
int S = solve(U[hi]), T = solve(V[hi]);
//TRACE(S _ T);
answer(S,T);
}
