#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
using namespace std;
// int Query(vector<bool> st);
// Answer(vector<int> res);
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
const int MaxN = 1007;
int n,m;
vi adj[MaxN];
pii a[MaxN];
void dfs(int u,int p,vi & lis) {
lis.pb(u);
for (int v : adj[u]) {
if (v == p) continue;
dfs(v,u,lis);
}
}
int Query_lis(vi lis) {
vector<int> tmp(n,0);
for (int x : lis) tmp[x-1] = 1;
return Query(tmp);
}
int Count(int pos,int i) {
vi tmp;
for (int i=1;i<=pos;i++) {
dfs(a[i].fi,-1,tmp);
}
tmp.pb(i);
return Query_lis(tmp);
}
void Solve(int N)
{
n = N;
m = 0;
for (int i=1;i<=n;i++) adj[i].clear();
for (int i=1;i<=N;i++) {
int l = 1 ,r = m;
int tmp = 1;
while (l <= r) {
int mid = (l+r) >> 1;
if (Count(mid,i) > mid) {
tmp = mid + 1;
l = mid + 1;
}
else r = mid - 1;
}
if (tmp > m) {
a[++m] = mp(i,i);
continue;
}
if (Query_lis({i,a[tmp].fi}) == 1) {
adj[a[tmp].fi].pb(i);
adj[i].pb(a[tmp].fi);
a[tmp].fi = i;
}
else {
adj[a[tmp].se].pb(i);
adj[i].pb(a[tmp].se);
a[tmp].se = i;
}
l = tmp + 1, r = m;
int tmpp = tmp + 1;
while (l <= r) {
int mid = (l+r) >> 1;
if (Count(mid,i) >= mid) {
tmpp = mid + 1;
l = mid + 1;
}
else r = mid - 1;
}
if (tmpp > m) continue;
if (Query_lis({a[tmpp].fi,i}) == 1) {
adj[a[tmpp].fi].pb(i);
adj[i].pb(a[tmpp].fi);
if (a[tmp].fi == i) a[tmp].fi = a[tmpp].se;
else a[tmp].se = a[tmpp].se;
}
else {
adj[a[tmpp].se].pb(i);
adj[i].pb(a[tmpp].se);
if (a[tmp].fi == i) a[tmp].fi = a[tmpp].fi;
else a[tmp].se = a[tmpp].fi;
}
int _m = 0;
for (int j=1;j<=m;j++) if (j != tmpp) a[++_m] = a[j];
m = _m;
}
vi res;
for (int i=1;i<=N;i++) if (adj[i].size() < 2) {
dfs(i,-1,res);
break;
}
Answer(res);
}
