#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 {

bool vis[N];
vector<int> Ans, ans;
int tcnt, lim;

inline void Dfs1(int f, vector<int> &rnk) {
  vis[f] = 1;
  ++tcnt;
  ans.push_back(f);
  if (ans.size() > Ans.size()) Ans = ans;
  if (ans.size() >= rnk.size()) return;
  for (auto t : rnk) {
    if (vis[t]) continue;
    if (!Ask({f}, {t})) continue;
    Dfs1(t, rnk);
    if (tcnt >= lim) return;
  }
  vis[f] = 0;
  ans.pop_back();
}

inline void Foo(vector<int> rnk) {
  if (Ans.size() >= rnk.size()) return;
  shuffle(begin(rnk), end(rnk), rnd);
  tcnt = 0, lim = 2 * n;
  ans.clear();
  Dfs1(rnk[0], rnk);
  for (auto x : rnk) vis[x] = 0;
}

inline vector<int> Work() {
  Ans.clear();
  vector<int> lian[2]{{1}, {}};
  rep (i, 2, n) {
    int id = Ask(lian[0], {i});
    lian[!id].push_back(i);
  }
  // dbg(lian[0], lian[1]);
  re (i, 10) {
    Foo(lian[0]);
    if (lian[1].size()) Foo(lian[1]);
  }
  return Ans;
}
}  // namespace st3

inline vector<int> Work() {
  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;
}