#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
constexpr int NN = 90000;
//#define int long long
typedef long long ll;
vector<pair<int,int>> g[NN];
vector<pair<int,int>> BFSTree[NN];
bool can[NN];
bool marked[NN];
bool wasL[NN],wasR[NN];
bool banned[NN];
void dfs(int v,int& c){
marked[v] = true;
c -= can[v];
for(auto&[to,id] : g[v]){
if(c > 0 && !marked[to]){
dfs(to,c);
}
}
return;
}
void dfsL(int v,int& c){
if(wasL[v]){
marked[v] = true;
c -= can[v];
}
for(auto&[to,id] : BFSTree[v]){
if(c > 0 && !marked[to] && wasL[to]){
dfsL(to,c);
}
}
return;
}
void dfsR(int v,int& c){
if(wasR[v]){
marked[v] = true;
c -= can[v];
}
for(auto&[to,id] : BFSTree[v]){
if(c > 0 && !marked[to] && wasR[to]){
dfsR(to,c);
}
}
return;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
int m = U.size();
for(int i = 0; i < m; i++){
g[U[i]].push_back(make_pair(V[i],i));
g[V[i]].push_back(make_pair(U[i],i));
}
vector<int> w(m,0);
ll minVal = ask(w);
for(int i = 0; i < N; i++){
can[i] = true;
}
int edgeID = -1;
{
vector<int> v;
for(int i = 0; i < m; i++) v.push_back(i);
bool s[m];
for(int i = 0; i < m; i++){
s[i] = 0;
}
while(v.size() > 1){
vector<int> L,R;
for(auto& id : v){
if(R.size() < L.size())
R.push_back(id);
else
L.push_back(id);
}
for(int i = 0; i < m; i++) w[i] = s[i];
for(auto& id : L) w[id] = 1;
ll val1 = ask(w);
if(val1 > minVal){
v = L;
}
else {
for(auto& id : L) s[id] = true;
v = R;
}
}
assert(!v.empty());
edgeID = v[0];
}
vector<int> BFSEdges;
{
bool used[N];
memset(used,0,sizeof used);
queue<int> q;
q.push(U[edgeID]);
used[U[edgeID]] = true;
q.push(V[edgeID]);
used[V[edgeID]] = true;
BFSEdges.push_back(edgeID);
while(!q.empty()){
int v = q.front();
q.pop();
for(auto&[to,id] : g[v]){
if(!used[to]){
used[to] = true;
q.push(to);
BFSEdges.push_back(id);
BFSTree[v].push_back(make_pair(to,id));
BFSTree[to].push_back(make_pair(v,id));
}
}
}
}
{
int u = U[edgeID], v = V[edgeID];
banned[u] = banned[v] = true;
queue<int> q;
q.push(u);
while(!q.empty()){
int vv = q.front();
wasL[vv] = true;
can[vv] = true;
q.pop();
for(auto&[to,id] : BFSTree[vv]){
if(!banned[to] && !wasL[to]){
wasL[to] = true;
can[to] = true;
q.push(to);
}
}
}
q.push(v);
while(!q.empty()){
int vv = q.front();
q.pop();
wasR[vv] = true;
can[vv] = true;
for(auto&[to,id] : BFSTree[vv]){
if(!banned[to] && !wasR[to]){
wasR[to] = true;
can[to] = true;
q.push(to);
}
}
}
}
bool notInBFSTRee[m];
for(int i = 0; i < m; i++) notInBFSTRee[i] = true;
for(auto& id : BFSEdges) notInBFSTRee[id] = false;
int s,t;
s = t = -1;
{
int root = U[edgeID];
int cnt = 0;
for(int i = 0; i < N; i++){
if(wasL[i]){
cnt += can[i];
}
}
while(cnt > 1){
for(int i = 0; i < N; i++) marked[i] = false;
int c = cnt/2;
dfsL(root,c);
for(int i = 0; i < m; i++) w[i] = notInBFSTRee[i];
for(int i = 0; i < N; i++){
for(auto&[to,id] : g[i]){
if(marked[i] && !marked[to] && !banned[to])
w[id] = true;
}
}
if(ask(w) > minVal){
for(int i = 0; i < N; i++){
if(wasL[i] && marked[i])
can[i] = false;
}
} else {
for(int i = 0; i < N; i++){
if(wasL[i] && !marked[i])
can[i] = false;
}
}
cnt = 0;
for(int i = 0; i < N; i++){
if(wasL[i])
cnt += can[i];
}
}
for(int i = 0; i < N; i++){
if(wasL[i] && can[i])
s = i;
}
}
{
int root = V[edgeID];
int cnt = 0;
for(int i = 0; i < N; i++){
if(wasR[i])
cnt += can[i];
}
while(cnt > 1){
for(int i = 0; i < N; i++) marked[i] = false;
int c = cnt/2;
dfsR(root,c);
for(int i = 0; i < m; i++) w[i] = notInBFSTRee[i];
for(int i = 0; i < N; i++){
for(auto&[to,id] : g[i]){
if(marked[i] && !marked[to] && !banned[to])
w[id] = true;
}
}
if(ask(w) > minVal){
for(int i = 0; i < N; i++){
if(wasR[i] && marked[i])
can[i] = false;
}
} else {
for(int i = 0; i < N; i++){
if(wasR[i] && !marked[i])
can[i] = false;
}
}
cnt = 0;
for(int i = 0; i < N; i++){
if(wasR[i])
cnt += can[i];
}
}
for(int i = 0; i < N; i++){
if(wasR[i] && can[i])
t = i;
}
}
answer(s,t);
return;
}
