#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif
/*
int hoursRequired(int X, int Y) {
cout << X << " " << Y << endl;
int p;
cin >> p;
return p;
}
*/
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
vector<int> createFunTour(int N, int Q) {
int n = N;
vector<vector<int>> adj(n);
if (n <= 600) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hoursRequired(i, j) == 1) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
} else {
for (int i = 1; i < n; i++) {
int x = i;
int y = (i - 1) / 2;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
vector<bool> block(n);
auto findFarthest = [&](int x) {
vector<int> d(n, -1);
d[x] = 0;
queue<int> que;
que.push(x);
while (!que.empty()) {
auto u = que.front();
que.pop();
for (auto v : adj[u]) {
if (d[v] == -1 && !block[v]) {
d[v] = d[u] + 1;
que.push(v);
}
}
}
return max_element(d.begin(), d.end()) - d.begin();
};
int fendPoint = findFarthest(0);
int sendPoint = findFarthest(fendPoint);
/*
contains pairs (depth, node) sorted by non-decreasing depth
*/
vector<pair<int, int>> st_first;
vector<pair<int, int>> st_second;
function<void(int, int, int, bool)> Dfs = [&](int u, int prev, int depth, bool which) {
if (which) {
st_second.push_back({depth, u});
} else {
st_first.push_back({depth, u});
}
for (auto v : adj[u]) {
if (v == prev) {
continue;
}
Dfs(v, u, depth + 1, which);
}
};
Dfs(fendPoint, -1, 0, 0);
Dfs(sendPoint, -1, 0, 1);
sort(st_first.begin(), st_first.end());
sort(st_second.begin(), st_second.end());
vector<int> perm;
perm.push_back(fendPoint);
perm.push_back(sendPoint);
block[fendPoint] = block[sendPoint] = true;
for (int it = 0; ; it++) {
if (it % 2 == 0) {
while (!st_second.empty()) {
auto x = st_second.back();
if (block[x.second]) {
st_second.pop_back();
} else {
perm.push_back(x.second);
block[x.second] = true;
st_second.pop_back();
break;
}
}
} else {
while (!st_first.empty()) {
auto x = st_first.back();
if (block[x.second]) {
st_first.pop_back();
} else {
perm.push_back(x.second);
block[x.second] = true;
st_first.pop_back();
break;
}
st_first.pop_back();
}
}
debug(perm);
if ((int) perm.size() == n) {
break;
}
}
return perm;
}
/*
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
vector<int> res = createFunTour(7, 40000);
debug(res);
return 0;
}
*/
