#include<bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long ll;
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
int n;
const int maxN=5000 + 15;
int a[maxN],b[maxN];
int con[maxN];
int tryCombination(int s[]);
void answer(int S[],int D[]);
bool open(int *p, int &k){
int a=tryCombination(p);
if(a==-1||a>k) return 1;
return 0;
}
void exploreCave(int n){
int s[n],d[n],ans[n];
for(int i=0;i<n;i++) s[i]=-1;
for(int i=0;i<n;i++){
vector<int> c;
for(int i=0;i<n;i++) if(s[i]==-1) c.push_back(i);
int p[n];
for(int i=0;i<n;i++){
if(s[i]==-1) p[i]=0;
else p[i]=s[i];
}
if(open(p,i)) ans[i]=0;
else ans[i]=1;
int st=0,end=c.size()-1,mid;
while(st<end){
for(auto x:c) p[x]=ans[i]^1;
mid=(st+end)/2;
for(int j=st;j<=mid;j++) p[c[j]]=ans[i];
if(open(p,i)) end=mid;
else st=mid+1;
}
d[c[st]]=i;
s[c[st]]=ans[i];
}
answer(s,d);
}
