#include "voltage.h"
#include "bits/stdc++.h"
#define vi vector<int>
#define pb push_back
#define sz(x) (int) (x).size()
#define pii pair<int, int>
using namespace std;
/*
-1: fst larger
0: same
1: snd larger
*/
int query_wrap(vi x, vi y) {
int q = query(x, y);
// cout << "? ";
// cout << "[";
// for (int z: x) cout << z;
// cout << "] [";
// for (int z: y) cout << z;
// cout << "] = " << q << "\n";
return q;
}
int N_;
bool solve(int N, int M) {
N_ = N;
vi prv(N, 0);
int deadend[N];
for (int i=0; i<N; i++) {
vi all(N, 0);
all[i] = 1;
vi real(N, 0);
if (query_wrap(real, all) == 0) deadend[i] = 1;
else deadend[i] = 0;
}
bool unsure[N];
queue<int> q;
for (int i=0; i<N; i++) {
if (!deadend[i]) {
unsure[i] = 1;
}
else {
q.push(i);
unsure[i] = 0;
}
}
vector<pii> edges;
vi adj[N];
bool vis[N];
for (int i=0; i<N; i++) vis[i] = 0;
while (sz(q)) {
int f = q.front();
q.pop();
vis[f] = 1;
// cout << "visited " << f << "\n";
vi allunsure;
for (int i=0; i<N; i++) if (unsure[i]) allunsure.pb(i);
if (!sz(allunsure)) break;
vi fr;
// cout << "unsure: ";
// for (int x: allunsure) cout << x << " ";
// cout << "\n";
while (1) {
int lb = 0, rb = sz(allunsure);
while (lb < rb) {
int mid = (lb + rb) >> 1;
vi on(N), off(N);
for (int i=0; i<=mid; i++) on[allunsure[i]] = off[allunsure[i]] = 1;
for (int i=0; i<N; i++) if (vis[i]) on[i] = off[i] = 1;
off[f] = 0, on[f] = 1;
if (query_wrap(off, on) == 0) lb = mid + 1;
else rb = mid;
}
if (lb == sz(allunsure)) break;
fr.pb(allunsure[lb]);
for (int i=0; i<=lb; i++) allunsure.erase(allunsure.begin());
}
for (int x: fr) {
vi off(N, 0);
for (int i=0; i<N; i++) {
if (vis[i]) off[i] = 1;
}
vi on;
on = off;
on[x] = 1;
// cout << "found " << x << " -> " << f << "\n";
edges.pb({x, f});
adj[x].pb(f);
if (query_wrap(on, off) == 0) {
q.push(x);
unsure[x] = 0;
// cout << "mark " << x << " as done\n";
}
}
}
if (sz(edges) != M) return false;
for (auto [u, v] : edges) answer(u, v);
return true;
}
