#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;
  int xn,deg[N],e[N][N];
}

int qry(int x,int y) {
  if(e[x][y]) return e[x][y];
  if(Query(x,y)) e[x][y]=1, e[y][x]=-1;
  else e[x][y]=-1, e[y][x]=1;
  return e[x][y];
}

vi solvesmall(vi p) {
  int n=p.size();
  rep(i,0,xn-1) deg[i]=0;
  rep(i,0,n-1) rep(j,i+1,n-1) qry(p[i],p[j]);
  rep(i,0,n-1) rep(j,0,n-1) deg[p[i]]+=(e[p[i]][p[j]]>0);
  int l=0, r=0;
  rep(i,0,n-1) if(deg[p[i]]==0) l=1;
  rep(i,0,n-1) if(deg[p[i]]==n-1) r=1;
  if(l&&r) return {l,r,0};
  else if(l) return {l};
  else if(r) return {0,r};
  vi q(n);
  rep(i,0,n-1) q[i]=-1;
  rep(i,0,n-1) {
    int u=p[i];
    if(deg[u]==l+1) {
      if(q[l+1]==-1) q[l+1]=u;
      else q[l+0]=u;
    } else if(deg[u]==n-2-r) {
      if(q[n-2-r]==-1) q[n-2-r]=u;
      else q[n-1-r]=u;
    } else q[deg[u]]=u;
  }
  if(qry(q[l],q[l+1])==-1) swap(q[l],q[l+1]);
  if(qry(q[n-2-r],q[n-1-r])==-1) swap(q[n-2-r],q[n-1-r]);
  return q;
}

vi Solve(int n) {
  vi p={0}; xn=n;
  if(n>8) {
    rep(i,1,n-1) {
      int x=qry(p[0],i), y=qry(p[i-1],i);
      //cout<<"  "<<x<<" "<<y<<endl;
      if(x==1) p.insert(p.begin(),i);
      else if(y==-1) p.insert(p.end(),i);
      else {
        int l=0, r=i-1;
        while(l<r) {
          int mid=l+r>>1;
          if(qry(p[mid],i)==1) r=mid;
          else l=mid+1;
        }
        p.insert(p.begin()+r,i);
      }
      //for(int x:p) cout<<x<<" "; puts("");
    }
    rep(i,0,n-2) assert(qry(p[i],p[i+1])==-1);
    int lb=4,rb=n-5;
    vi t={p[0],p[1],p[2],p[3]}; t=solvesmall(t);
    if(t.size()==4) {
      bool flag=1;
      rep(i,0,3) flag|=(p[i]==t[3-i]);
      if(flag) lb=0;
      else rep(i,0,3) p[i]=t[i];
    } else if(t.size()==3) lb=2;
    else if(t.size()==2) lb=3;
    else if(t.size()==1) lb=1;
    t={p[n-4],p[n-3],p[n-2],p[n-1]}; t=solvesmall(t);
    if(t.size()==4) {
      bool flag=1;
      rep(i,0,3) flag|=(p[n-4+i]==t[3-i]);
      if(flag) rb=n-1;
      else rep(i,0,3) p[n-4+i]=t[i];
    } else if(t.size()==3) rb=n-3;
    else if(t.size()==2) rb=n-2;
    else if(t.size()==1) rb=n-4;
    //for(int x:p) cout<<x<<" "; puts("");
    //cout<<"JIE "<<lb<<" "<<rb<<endl;
    rep(i,lb,rb) {
      int j=i+2; if(j>rb) break;
      if(i>0&&qry(p[i-1],p[i])==1) continue;
      while(j<=rb&&qry(p[i],p[j])==1) j++;
      //cout<<j<<endl;
      if(j!=rb+1&&j!=i+2&&qry(p[i+1],p[j-1])==-1) --j;
      //cout<<i<<" "<<j<<endl;
      reverse(p.begin()+i,p.begin()+j);
      i=j-1;
    }
    if(qry(p[rb-1],p[rb])==-1) swap(p[rb-1],p[rb]);
    //for(int x:p) cout<<x<<" "; puts("");
    t={p[0],p[1],p[2],p[3]}; t=solvesmall(t);
    rep(i,0,3) p[i]=t[i];
    //for(int x:p) cout<<x<<" "; puts("");
    t={p[n-4],p[n-3],p[n-2],p[n-1]}; t=solvesmall(t);
    rep(i,0,3) p[n-4+i]=t[i];
    //for(int x:p) cout<<x<<" "; puts("");
  } else {
    rep(i,1,n-1) p.eb(i);
    p=solvesmall(p);
  }
  vi q(n);
  rep(i,0,n-1) q[p[i]]=i;
  return q;
}