#include "monster.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii; 
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

namespace {
  const int N=1005;
  mt19937 rnd;
  int deg[N],e[N][N];
}

vi work(vi p,int l,int r) {
  if(p.size()==1) return p;
  if(p.size()<=6) {
    int n=p.size();
    rep(i,0,n-1) rep(j,i+1,n-1) {
      int u=p[i], v=p[j];
      e[u][v]=Query(u,v), e[v][u]=!e[u][v];
      if(e[u][v]) deg[u]++;
      else deg[v]++;
    }
    vi q(n);
    rep(i,0,n-1) {
      int u=p[i];
      if(deg[u]==1+l) {
        if(!q[1+l]) q[1+l]=u+1;
        else q[0+l]=u+1;
      } else if(deg[u]==n-2-r) {
        if(!q[n-2-r]) q[n-2-r]=u+1;
        else q[n-1-r]=u+1;
      } else q[deg[u]]=u+1;
    }
    for(int &x:q) --x;
    if(p.size()-l-r>1) {
      if(!e[q[l]][q[l+1]]) swap(q[l],q[l+1]);
      if(p.size()-l-r>2&&!e[q[n-2-r]][q[n-1-r]]) swap(q[n-2-r],q[n-1-r]);
    }
    return q;
  }
  assert(p.size());
  int n=p.size(); int x=p[rnd()%n];
  vi pl,pr;
  for(int y:p) if(y!=x) {
    if(Query(x,y)) pl.eb(y);
    else pr.eb(y);
  }
  while(pl.size()<=2||pr.size()<=2||pl.size()-l-1==3||pr.size()-r-1==3) {
    x=p[rnd()%n];
    pl.clear(), pr.clear();
    for(int y:p) if(y!=x) {
      if(Query(x,y)) pl.eb(y);
      else pr.eb(y);
    }
  }
  if(pr.size()==0) {
    p=work(pl,l,0); p.eb(x);
    return p;
  } else if(pl.size()==0) {
    p={x}; vi q=work(pr,0,r);
    p.insert(p.end(),q.begin(),q.end());
    return p;
  } else {
    pl=work(pl,l||(pl.size()==2),1);
    pr=work(pr,1,r||(pr.size()==2));
    int sl=pl.size(), sr=pr.size();
    vi q;
    rep(i,0,sl-2) q.eb(pl[i]);
    q.eb(pr[0]), q.eb(x), q.eb(pl[sl-1]);
    rep(i,1,sr-1) q.eb(pr[i]);
    return q;
  }
}

vi Solve(int n) {
  vi p; rep(i,0,n-1) p.eb(i);
  p=work(p,0,0); vi q(n);
  rep(i,0,n-1) q[p[i]]=i;
  return q;
}