#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define ins insert
const int MOD = 1000000007;
const int mx = 90005;
int N, M;
ll A, B;
int D;
ll reg;
vi U, V;
vi adj[mx]; //node, edge
int dist[mx][2];
void genDist(int node, int typ){
queue<int> q;
dist[node][typ] = 0;
q.push(node);
while(sz(q)){
int a = q.front();
q.pop();
for(auto u: adj[a]){
if(dist[u][typ] > dist[a][typ]+1){
dist[u][typ] = dist[a][typ]+1;
q.push(u);
}
}
}
}
vi curw;
vpi tadj[mx];
vi ord; //nodes, ordered by postorder
int tdist[mx];
vi children[mx];
pi par[mx];
void genTDist(int node){
queue<int> q;
tdist[node] = 0;
q.push(node);
while(sz(q)){
int a = q.front();
q.pop();
for(auto u: tadj[a]){
if(tdist[u.f] > tdist[a]+1){
tdist[u.f] = tdist[a]+1;
q.push(u.f);
}
}
}
}
void genPO(int node){
for(auto u: children[node]){
genPO(u);
}
ord.pb(node);
}
int treeAns(vector<pair<pi, int>> eds, int R){
set<int> trash;
for(auto u: eds){
trash.ins(u.f.f); trash.ins(u.f.s);
}
trash.ins(R);
vi nodes;
for(auto u: trash) nodes.pb(u);
// cout << "nodes: ";
// for(auto u: nodes) cout << u << " ";
// cout << "\n";
// cout << sz(nodes) << "\n";
ord.clear();
for(auto u: nodes){
tadj[u].clear();
children[u].clear();
par[u] = mp(-1, -1);
}
for(auto u: eds){
tadj[u.f.f].pb(mp(u.f.s, u.s));
tadj[u.f.s].pb(mp(u.f.f, u.s));
}
for(auto u: nodes) tdist[u] = MOD;
genTDist(R);
//for(auto u: nodes) cout << u << " " << tdist[u] << "\n";
vi tw = curw;
for(auto u: nodes){
if(u == R) continue;
bool found = 0;
for(auto x: tadj[u]){
if(tdist[x.f]+1 != tdist[u]) continue;
if(!found){
found = 1;
children[x.f].pb(u);
par[u] = x;
//cout << "ED: " << x.f << " " << x.s << " " << u << "\n";
}
else{
//cout << x.s << "\n";
tw[x.s] = 1;
}
}
}
genPO(R);
// cout << "ord: ";
// for(auto u: ord) cout << u << " ";
// cout << "\n";
// cout << "tw: ";
// for(auto u: tw) cout << u << " ";
// cout << "\n";
int lo = 0;
int hi = sz(ord)-1;
while(lo < hi){
int mid = (lo+hi)/2;
vi w = tw;
for(int i = 0; i <= mid; i++){
w[par[ord[i]].s] = 1;
}
if(ask(w) != reg){
hi = mid;
}
else{
lo = mid+1;
}
}
return ord[lo];
}
void find_pair(int _N, vi _U, vi _V, int _A, int _B) {
N = _N;
U = _U;
V = _V;
M = sz(U);
A = _A;
B = _B;
reg = ask(vi(M, 0));
//perhaps random shuffle?
int lo = 1;
int hi = M;
while(lo < hi){
int mid = (lo+hi)/2;
vi w(M, 0);
for(int i = 0; i < mid; i++) w[i] = 1;
ll res = ask(w);
if(res == reg){
lo = mid+1;
}
else hi = mid;
}
for(int i = lo; i < M; i++){
adj[U[i]].pb(V[i]);
adj[V[i]].pb(U[i]);
}
//cout << lo << "\n";
for(int j = 0; j < 2; j++){
for(int i = 0; i < N; i++){
dist[i][j] = MOD;
}
}
genDist(U[lo-1], 0);
genDist(V[lo-1], 1);
//cout << dist[3][0] << " " << dist[3][1] << "\n";
vector<pair<pi, int>> tr[2];
for(int i = lo; i < M; i++){
int typ1 = -1;
int typ2 = -1;
int typ;
if(dist[U[i]][0] < dist[U[i]][1]){
typ1 = 0;
}
else if(dist[U[i]][0] > dist[U[i]][1]){
typ1 = 1;
}
if(dist[V[i]][0] < dist[V[i]][1]){
typ2 = 0;
}
else if(dist[V[i]][0] > dist[V[i]][1]){
typ2 = 1;
}
if(typ1 != typ2) continue;
typ = typ1;
if(typ == -1) continue;
tr[typ].pb(mp(mp(U[i], V[i]), i));
}
curw = vi(M, 0);
for(int i = 0; i < lo-1; i++){
curw[i] = 1;
}
int a = treeAns(tr[0], U[lo-1]);
int b = treeAns(tr[1], V[lo-1]);
//cout << a << " " << b << "\n";
answer(a, b);
}
