#include <bits/stdc++.h>
#include "cave.h"
#define mp make_pair
#define mt make_tuple
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = 1LL<<62;
const int INF = 1<<30;
const int MAXN = 0;
int tryCombination(int S[]);
void answer(int S[],int D[]);
void exploreCave(int N){
int combination[N], link[N];
int it[N];
for(int i = 0; i < N; i++){
combination[i] = -1;
it[i] = 0;
link[i] = -1;
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++)
it[j] = combination[j] == -1 ? 0 : combination[j];
int cur = tryCombination(it);
if(cur == -1 || cur > i) cur = 0;
else cur = 1;
int ini = 0, fim = N;
while(fim!=ini){
int m = (ini+fim)/2;
for(int j = 0; j < N; j++){
if(link[j] == -1){
if(ini <= j && j <= m)
it[j] = cur;
else it[j] = (cur+1)&1;
} else it[j] = combination[j];
}
int test = tryCombination(it);
if(test > i || test == -1)
fim = m;
else ini = m+1;
}
link[ini] = i;
combination[ini] = cur;
}
answer(combination,link);
}
