#include <bits/stdc++.h>
#define ll long long
#define io(x) if (fopen(x".inp","r")) {freopen(x".inp","r",stdin),freopen(x".out","w",stdout);}
#define TimeRun {End=clock();cerr<<"Time run: "<<(float)(End-Begin)/CLOCKS_PER_SEC<<"s"<<el;}
#define mem(c, x) memset(c, x, sizeof(c))
#define all(c) c.begin(), c.end()
#define bit(i,j) ((i >> j) & 1)
#define se second
#define fi first
#define el '\n'
using namespace std;
template<class X, class Y> bool maximize(X &a, const Y &b) { return (a < b ? a = b, 1 : 0); }
template<class X, class Y> bool minimize(X &a, const Y &b) { return (a > b ? a = b, 1 : 0); }
int dx[8] = {0, 1, 0,-1, 1, 1,-1,-1};
int dy[8] = {1, 0,-1, 0, 1,-1,-1, 1};
const int maxn = 1e5 + 9;
const int Inf = 2e9 + 7;
const ll Infll = 1e18 + 9;
const ll Mod = 1e9 + 7;
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
int tryCombination(vector<int> s);
void answer(vector<int> s, vector<int> d);
set<int> st;
void exploreCave(int N) {
vector<int> s(N, 0), d(N, 0);
for (int i = 0; i < N; i++) st.insert(i);
while (true) {
int firstClosed = tryCombination(s);
if (firstClosed == -1) break;
for (auto it = st.begin(); it != st.end();) {
int pos = *it;
s[pos] ^= 1;
int pp = tryCombination(s);
if (pp == -1) break;
if (pp < firstClosed) {
s[pos] ^= 1;
d[pos] = pp;
it = st.erase(it);
} else if (pp > firstClosed) {
d[pos] = firstClosed;
it = st.erase(it);
break;
} else { // pp == firstClosed
s[pos] ^= 1;
++it;
}
}
}
answer(s, d);
}
