#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5e3+7;
int t1[MAXN], t2[MAXN], res[MAXN], t3[MAXN];
int xd,p,k,s;
/*int n;
int comb[MAXN], dop[MAXN],sol[MAXN];
int tryCombination(int t[]){
for(int i=0;i<n;i++) if(t[i]!=sol[i]) return i;
return -1;
}
void answer(int a[],int b[]){
for(int i=0;i<n;i++) if(a[i]!=comb[i]) {cout<<"WA\n"; return;}
for(int i=0;i<n;i++) if(b[i]!=dop[i]){cout<<"WA\n"; return;}
cout<<"OK\n";
}*/
void exploreCave(int N){
for(int i=0;i<N;i++){
xd=0,p=0,k=N-1;
for(int j=0;j<N;j++) t1[j]=0;
for(int j=0;j<i;j++) t1[t3[j]]=t2[t3[j]];
if(tryCombination(t1)==i) xd++;
while(p<k){
s=(p+k)/2;
for(int j=0;j<N;j++) t1[j]=1-xd;
for(int j=p;j<=s;j++) t1[j]=xd;
for(int j=0;j<i;j++) t1[t3[j]]=t2[t3[j]];
if(tryCombination(t1)==i) p=s+1;
else k=s;
}
//cout<<"p="<<p<<'\n';
t3[i]=p;
t2[t3[i]]=xd;
}
for(int i=0;i<N;i++) res[t3[i]]=i;
//for(int i=0;i<n;i++) cout<<t2[i]<<' '; cout<<'\n';
//for(int i=0;i<n;i++) cout<<res[i]<<' '; cout<<'\n';
answer(t2,res);
}/*
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>comb[i];
for(int i=0;i<n;i++) cin>>dop[i];
for(int i=0;i<n;i++) sol[dop[i]]=comb[i];
for(int i=0;i<n;i++) cout<<sol[i]<<' ';
exploreCave(n);
return 0;
}*/
