#include "library.h"
#include <bits/stdc++.h>
#define C(a, b) ed[a].push_back(b), ed[b].push_back(a);
using namespace std;
int k, l[1010], s, e, d, bf, kk;
map<int, int> t;
vector<int> ed[1010], rs;
void dfs(int x, int f) {
rs.push_back(x);
for (auto i : ed[x])
if (i != f)
dfs(i, x);
}
void Solve(int n) {
vector<int> m(n), p;
m[0] = 1, t[1] = 1, bf = 1;
for (int i = 2; i <= n; i++) {
m[i - 1] = 1, k = Query(m);
if (k > bf)
t[i] = i;
else {
vector<int> b;
for (auto [l, r] : t)
if (l < r)
b.push_back(l);
for (auto [l, r] : t)
if (l == r)
b.push_back(l);
for (auto [l, r] : t)
if (l > r)
b.push_back(l);
for (s = 0, e = b.size() - 1; s < e;) {
p = m, d = s + e >> 1, kk = k;
for (int i = s; i <= d; i++)
p[b[i] - 1] = 0, kk -= t[b[i]] == b[i];
if (Query(p) > kk)
e = d;
else
s = d + 1;
}
int x = b[s], y = t[b[s]];
t[y] = i, t[i] = y;
if (x ^ y)
t.erase(x);
C(x, i);
if (k < bf) {
b.erase(b.begin() + s);
if (x ^ y)
b.erase(find(b.begin(), b.end(), y));
for (s = 0, e = b.size() - 1; s < e;) {
p = m, d = s + e >> 1, kk = k;
for (int i = s; i <= d; i++)
p[b[i] - 1] = 0, kk -= t[b[i]] == b[i];
if (Query(p) > kk)
e = d;
else
s = d + 1;
}
int x = b[s], y = t[b[s]], z = t[i];
t[y] = z, t[z] = y, t.erase(i);
if (x ^ y)
t.erase(x);
C(x, i);
}
}
bf = k;
}
for (int i = 1; i <= n; i++) {
if (ed[i].size() < 2) {
dfs(i, 0);
Answer(rs);
return;
}
}
}
