#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 {
const int N = 1009;
mt19937 rnd;
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);
}

namespace st2 {
bool vis[N];
int rnk[N];
vector<int> ans;
inline void Dfs1(int f) {
  vis[f] = 1;
  ans.push_back(f);
  if ((int)ans.size() == n) return;
  re (i, n) {
    int t = rnk[i];
    if (vis[t]) continue;
    if (!Ask({f}, {t})) continue;
    Dfs1(t);
    if ((int)ans.size() == n) return;
  }
  vis[f] = 0;
  ans.pop_back();
}
inline vector<int> Work() {
  ans.clear();
  re (i, n) rnk[i] = i;
  while ((int)ans.size() != n) {
    ans.clear();
    re (i, n) vis[i] = 0;
    shuffle(rnk + 1, rnk + n + 1, rnd);
    Dfs1(rnk[1]);
  }
  return ans;
}
}  // namespace st2

namespace st3 {

int rnk[N];

inline vector<int> Work() {
  re (i, n) rnk[i] = i;
  shuffle(rnk + 1, rnk + n + 1, rnd);
  vector<int> lian[2]{{rnk[1]}, {}};
  rep (ii, 2, n) {
    int i = rnk[ii];
    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);
    }
  }
  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];
    re (_, lian[1].size()) {
      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];
      }
      rotate(lian[1].begin(), lian[1].begin() + 1, lian[1].end());
    }
    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 st3

inline vector<int> Work() {
  // rnd.seed(0);
  if (m == 3) {
    vector<int> vec;
    re (i, n) vec.push_back(i);
    return vec;
  }
  if (m == 2) return st2::Work();
  return st3::Work();
}
}  // namespace qingwa

std::vector<int> longest_trip(int N, int D) {
  using namespace qingwa;
  if (!flinit) flinit = 1, rnd.seed(random_device()());
  n = N, m = D;
  auto vec = Work();
  for (auto &x : vec) --x;
  return vec;
}