#include<bits/stdc++.h>
#include "interactive.h"
using namespace std;
const int kmaxn=505;
vector<int>an;
int ip[kmaxn],now,dm[kmaxn][kmaxn],cnt[kmaxn][kmaxn];
double ppc[kmaxn][kmaxn];
int n;
bool pd[kmaxn];
bool cmp(int x,int y){
	return (ppc[now][x]/cnt[now][x])>(ppc[now][y]/cnt[now][y]);
}
void dfs(int x,int f){
	an.push_back(x);
	pd[x]=1;now=x;for(int i=1;i<=n;i++)ip[i]=i;
	sort(ip+1,ip+1+n,cmp);
	for(int I=1;I<=n;I++){
		int i=ip[I];
		if(dm[x][i]&&i!=f&&i!=x&&!pd[i]){
			dfs(i,x);
		}
	}
}
int cont(vector<int>x){
	int cp=0;
	for(int i=0;i<x.size()-1;i++){
		if(dm[x[i]][x[i+1]]==0)cp++;
	}
	return cp;
} 
bool cmd(vector<int>x,vector<int>y){
	return cont(x)>cont(y);
}
std::vector<int> solve(int N){
//	freopen("Md.out","w",stdout);
	n=N;
	srand(time(0));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dm[i][j]=1;
		}
	}
	vector<int>pr,O[10];
	for(int i=1;i<=n;i++){
		pr.push_back(i);
	}
	for(int I=1;I<18000;I++){
		for(int j=0;j<6;j++)random_shuffle(pr.begin(),pr.end()),O[j]=pr;
		sort(O+0,O+6,cmd);pr=O[0];
		int op=query(pr);
		if(n==3){
			if(op==2){
				return pr;
			}
		}
		for(int i=0;i<n-1;i++){
			int u=pr[i],v=pr[i+1];
			cnt[u][v]++,cnt[v][u]++;
			ppc[u][v]+=op;ppc[v][u]+=op;
			dm[u][v]=min(dm[u][v],op);
			dm[v][u]=min(dm[v][u],op);
		}
	}
	int pq=0;
	for(int i=1;i<=n;i++){
		int sz=0;
		for(int j=1;j<=n;j++){
			if(i!=j&&dm[i][j])sz++;
		}
		if(sz>2)pq++;
		if(sz==1){dfs(i,0);return an;}
	}
	return an;
}