#include "library.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, link[1005], sz[1005];
vector<int> M, vec, adj[1005];
vector<ii> rel;
int find(int x) {
if (x == link[x]) return x;
return link[x] = find(link[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
link[b] = a;
}
void fillM(int l, int r) {
for (int i = 0; i < N; i++) M[i] = 0;
for (int i = l; i <= r; i++) M[i] = 1;
}
void dfs(int n, int e = -1) {
vec.pb(n + 1);
for (auto u : adj[n]) if (u != e) dfs(u, n);
}
int comp(int l, int r) {
int ret = 0;
for (int i = 0; i < N; i++) {
link[i] = i;
sz[i] = 1;
}
for (auto [a, b] : rel)
if (l <= a && a <= r && l <= b && b <= r) unite(a, b);
for (int i = l; i <= r; i++)
if (i == link[i]) ret++;
return ret;
}
void Solve(int N) {
if (N == 1) {
vec.pb(1);
Answer(vec);
return;
}
::N = N;
M.resize(N);
for (int i = 0, prv = 0; i < N; i++) {
fillM(0, i);
int tmp = Query(M);
if (tmp == prv) {
int lo = 0, hi = i - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
fillM(mid, i);
if (comp(mid, i - 1) == Query(M)) ans = mid, lo = mid + 1;
else hi = mid - 1;
}
assert(ans != -1);
rel.eb(ans, i);
} else if (tmp == prv - 1) {
int lo = 0, hi = i - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
fillM(mid, i);
if (comp(mid, i - 1) >= Query(M)) ans = mid, lo = mid + 1;
else hi = mid - 1;
}
assert(ans != -1);
rel.eb(ans, i);
lo = 0, hi = i - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
fillM(mid, i);
if (comp(mid, i) != Query(M)) ans = mid, lo = mid + 1;
else hi = mid - 1;
}
assert(ans != -1);
rel.eb(ans, i);
}
prv = tmp;
}
for (auto [x, y] : rel) {
adj[x].pb(y);
adj[y].pb(x);
}
for (int i = 0; i < N; i++)
if (adj[i].size() == 1) {
dfs(i);
break;
}
Answer(vec);
}
