#include "cave.h"
//#include "grader.c"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ar array
#define mrand(a, b) uniform_int_distribution<int>(a, b)(rng)
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace FAST {
template<typename T, typename F>
istream &operator>>(istream &cin, pair<T, F> &p) {
cin >> p.first >> p.second;
return cin;
}
template<typename T, typename F>
ostream &operator<<(ostream &cout, pair<T, F> &p) {
cout << p.first << ' ' << p.second;
return cout;
}
template<typename T>
istream &operator>>(istream &cin, vector<T> &a) {
for (T &i: a) cin >> i;
return cin;
}
template<typename T>
ostream &operator<<(ostream &cout, vector<T> &a) {
for (T i: a) cout << i << ' ';
return cout;
}
template<typename T>
istream &operator>>(istream &cin, deque<T> &a) {
for (T &i: a) cin >> i;
return cin;
}
template<typename T>
ostream &operator<<(ostream &cout, deque<T> &a) {
for (T i: a) cout << i << ' ';
return cout;
}
}
using namespace FAST;
const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int md = 998244353;
int n,m,k;
void exploreCave(int N){
int q[N];
int val[N], ps[N], vla[N];
vector<ar<int,2>>vs;
for(int i = 0;i<N;i++){
for(int j = 0;j<N;j++){
q[j] = 0;
}
for(auto [to, pos] : vs){
q[to] = pos;
}
// for(int j = 0;j<N;j++){
// cout << q[j] << " ";
// }
// cout << " ";
int a = tryCombination(q);
// cout << a << "\n";
if(a > i || a == -1){
val[i] = 0;
}
else val[i] = 1;
int l = 0, r = N - 1, ans = -1;
while(l <= r){
int mid = (l + r) / 2;
for(int j = 0;j<=mid;j++){
q[j] = val[i];
}
for(int j = mid + 1;j<N;j++){
q[j] = (val[i] ^ 1);
}
for(auto [to, pos] : vs)
q[to] = pos;
a = tryCombination(q);
// if(i == 2){
// for(int j = 0;j<N;j++)cout << q[j] << " ";
// cout << "\n";
// cout << mid << " " << a << " " << val[i] << "\n";
// }
if(a > i || a == -1){
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
// cout << ans << "\n";
vs.pb({ans, val[i]});
vla[ans] = val[i];
ps[ans] = i;
// exit(0);
}
answer(vla, ps);
}
