#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 100010, MAX_D = 17;
int qdis(int a, int b) { return hoursRequired(a, b); }
int sbsz(int rt, int x) { return attractionsBehind(rt, x); }
// always go to the farthest point possible
// but it doesn't rely on deg(x) <= 3
int dep[MAX_N], in[MAX_N], out[MAX_N], anc[MAX_D][MAX_N];
vector<int> edge[MAX_N];
bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
int get_lca(int a, int b) {
if (isanc(a, b)) return a;
if (isanc(b, a)) return b;
for (int i = MAX_D-1;i >= 0;--i)
if (!isanc(anc[i][a], b))
a = anc[i][a];
return anc[0][a];
}
int dis(int a, int b) {
if (a > b) swap(a, b);
static map< pair<int,int>, int > mem;
return mem.count({a, b}) ? mem[{a, b}] : mem[{a, b}] = qdis(a, b);
return dep[a] + dep[b] - 2 * dep[get_lca(a, b)];
}
void dfs_init(int x, int lst) {
static int t;
anc[0][x] = lst;
for (int d = 1;d < MAX_D;++d)
anc[d][x] = anc[d-1][ anc[d-1][x] ];
in[x] = t++;
for (int u : edge[x]) if (u != lst) {
dep[u] = dep[x] + 1;
dfs_init(u, x);
}
out[x] = t;
}
struct node {
vector<int> cand;
node () {}
node (vector<int> c) : cand(c) {}
node (node a, node b) {
cand = a.cand;
for (int u : b.cand) {
if (cand.size() <= 1) {
cand.pb(u);
continue;
}
int &x = cand[0], &y = cand[1];
int da = dis(u, x), db = dis(u, y);
if (da < db) swap(da, db), swap(x, y);
if (da <= dis(x, y)) continue;
y = u;
}
};
};
struct sgt {
int n;
vector<node> val;
sgt(int n) : n(n) {
val.resize(n<<1);
for (int i = 0;i < n;++i)
val[i+n] = node({i});
for (int i = n-1;i > 0;--i)
val[i] = node(val[i<<1], val[i<<1|1]);
}
void kill(int i) {
val[i+n] = node();
for (i += n;i>>=1;) {
val[i] = node(val[i<<1], val[i<<1|1]);
}
}
vector<int> qry() {
return val[1].cand;
}
};
vector<int> gen_ans(int N, vector<pair<int,int>> alle) {
// for (auto [a, b] : alle) {
// edge[a].pb(b), edge[b].pb(a);
// }
//
// dfs_init(0, 0);
//
sgt tree(N);
int x = tree.qry()[0];
vector<int> res {x};
tree.kill(x);
for (int i = 1;i < N;++i) {
auto vec = tree.qry();
int a = vec[0], b = end(vec)[-1];
if (dis(x, b) > dis(x, a))
swap(a, b);
res.pb(x = a);
tree.kill(x);
}
return res;
}
std::vector<int> createFunTour(int N, int Q) {
vector<pair<int,int>> alle;
// for (int i = 1;i < N;++i)
// alle.pb(i, (i-1)/2);
//
// if (1ll * N * N / 2 <= 400000) {
// alle.clear();
// for (int i = 0;i < N;++i)
// for (int j = i+1;j < N;++j)
// if (qdis(i, j) == 1)
// alle.pb(i, j);
// }
return gen_ans(N, alle);
// vector<int> ans;
//
// vector<int> vis(N);
//
// assert(1ll * N * N <= Q);
//
// auto getfar = [&](int x) {
// int p = -1, d = -1;
// for (int i = 0;i < N;++i)
// if (x != i && !vis[i]) {
// if (chmax(d, qdis(x, i)))
// p = i;
// }
// return p;
// };
//
// ans.pb(getfar(0));
//
// for (int i = 1;i < N;++i) {
// vis[ans[i-1]] = true;
// ans.pb(getfar(ans[i-1]));
// }
//
// return ans;
}
