#include <bits/stdc++.h>

#include "longesttrip.h"

#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>

#include "grader.cpp"
#else
#define dbg(x...) (0)
#endif

using namespace std;

using ll = long long;

// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))

template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
  if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
  if (y < x) x = y;
}

namespace qingwa {
int n, m;
bool flinit;

inline bool Ask(vector<int> x, vector<int> y) {
  for (auto &v : x) --v;
  for (auto &v : y) --v;
  return are_connected(x, y);
}

inline vector<int> Work() {
  vector<int> lian[2]{{1}, {}};
  rep (i, 2, n) {
    if (i == n) {
      if (Ask({lian[0].back()}, {i}))
        lian[0].push_back(i);
      else if (lian[1].empty() || Ask({lian[1].back()}, {i}))
        lian[1].push_back(i);
      else {
        reverse(lian[1].begin(), lian[1].end());
        for (auto x : lian[1]) lian[0].push_back(x);
        lian[1].clear();
        lian[1].push_back(i);
      }
    } else {
      if (Ask({i}, {i + 1})) {
        if (Ask({lian[0].back()}, {i}))
          lian[0].push_back(i), lian[0].push_back(i + 1);
        else {
          if (lian[1].empty() || Ask({lian[1].back()}, {i}))
            lian[1].push_back(i), lian[1].push_back(i + 1);
          else {
            reverse(lian[1].begin(), lian[1].end());
            for (auto x : lian[1]) lian[0].push_back(x);
            lian[1].clear();
            lian[1].push_back(i);
            lian[1].push_back(i + 1);
          }
        }
      } else {
        if (Ask({lian[0].back()}, {i})) {
          lian[0].push_back(i);
          if (lian[1].empty() || Ask({lian[1].back()}, {i})) {
            reverse(lian[1].begin(), lian[1].end());
            for (auto x : lian[1]) lian[0].push_back(x);
            lian[1].clear();
          }
          lian[1].push_back(i + 1);
        } else {
          if (lian[1].empty() || Ask({lian[1].back()}, {i}))
            lian[1].push_back(i), lian[0].push_back(i + 1);
          else {
            lian[1].push_back(i + 1);
            reverse(lian[1].begin(), lian[1].end());
            for (auto x : lian[1]) lian[0].push_back(x);
            lian[1].clear();
            lian[1].push_back(i);
          }
        }
      }
      ++i;
    }
    // dbg(lian[0], lian[1]);
  }
  if (lian[0].size() < lian[1].size()) swap(lian[0], lian[1]);
  // dbg(lian[0], lian[1]);
  re (_, 2) {
    if (lian[1].empty()) return lian[0];
    if (Ask({lian[0].back()}, {lian[1][0]})) {
      for (auto x : lian[1]) lian[0].push_back(x);
      return lian[0];
    }
    if (Ask({lian[0].back()}, {lian[1].back()})) {
      reverse(lian[1].begin(), lian[1].end());
      for (auto x : lian[1]) lian[0].push_back(x);
      return lian[0];
    }
    swap(lian[0], lian[1]);
  }
  if (lian[0].size() < lian[1].size()) swap(lian[0], lian[1]);
  if (lian[1].empty() || !Ask(lian[0], lian[1])) return lian[0];
  // dbg(lian[0], lian[1]);
  int l = 0, r = lian[0].size() - 1;
  auto Ck1 = [&](int x) -> bool {
    vector<int> vec;
    rep (i, 0, x) vec.push_back(lian[0][i]);
    return Ask(vec, lian[1]);
  };
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (Ck1(mid))
      r = mid;
    else
      l = mid + 1;
  }
  int p0 = Ck1(l) ? l : r;
  l = 0, r = lian[1].size() - 1;
  auto Ck2 = [&](int x) -> bool {
    vector<int> vec;
    rep (i, 0, x) vec.push_back(lian[1][i]);
    return Ask({lian[0][p0]}, vec);
  };
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (Ck2(mid))
      r = mid;
    else
      l = mid + 1;
  }
  int p1 = Ck2(l) ? l : r;
  // dbg(p0, p1);
  vector<int> ans;
  rep (i, p0 + 1, lian[0].size() - 1) ans.push_back(lian[0][i]);
  rep (i, 0, p0) ans.push_back(lian[0][i]);
  rep (i, p1, lian[1].size() - 1) ans.push_back(lian[1][i]);
  rep (i, 0, p1 - 1) ans.push_back(lian[1][i]);
  return ans;
}
}  // namespace qingwa

std::vector<int> longest_trip(int N, int D) {
  using namespace qingwa;
  n = N, m = D;
  auto vec = Work();
  for (auto &x : vec) --x;
  return vec;
}