/**
 * @file qoj7119.cpp
 * @author n685
 * @brief
 * @date 2023-12-27
 *
 *
 */
#include "longesttrip.h"
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

std::vector<int> longest_trip(int N, int D) {
  int n = N;
  std::vector<int> ind(n);
  std::iota(ind.begin(), ind.end(), 0);
  std::shuffle(ind.begin(), ind.end(), rng);

  auto query = [&](std::vector<int> a, std::vector<int> b) {
    std::vector<int> A(a.size()), B(b.size());
    for (int i = 0; i < (int)a.size(); ++i) {
      A[i] = ind[a[i]];
    }
    for (int i = 0; i < (int)b.size(); ++i) {
      B[i] = ind[b[i]];
    }
    return are_connected(A, B);
  };

  std::vector<std::vector<int>> gr;
  for (int i = 0; i < n; ++i) {
    gr.push_back(std::vector{i});
  }
  auto merge = [&](auto &a, auto &b) {
    if ((int)a.size() < (int)b.size()) {
      std::swap(a, b);
    }
    std::reverse(a.begin(), a.end());
    for (int i : b) {
      a.push_back(i);
    }
    b.clear();
  };

  while (gr.size() >= 3) {
    auto ga = gr.back(), gb = gr.end()[-2], gc = gr.end()[-3];
    gr.pop_back(), gr.pop_back(), gr.pop_back();
    if (query({ga[0]}, {gb[0]})) {
      std::swap(ga, gc);
    } else if (query({ga[0]}, {gc[0]})) {
      std::swap(ga, gb);
    }
    merge(gb, gc);
    gr.push_back(ga);
    gr.push_back(gb);
  }

  auto answer = [&](const std::vector<int> &seq) {
    std::vector<int> ans;
    for (int i : seq) {
      ans.push_back(ind[i]);
    }
    return ans;
  };
  if (!query(gr[0], gr[1])) {
    if ((int)gr[0].size() < (int)gr[1].size()) {
      std::swap(gr[0], gr[1]);
    }
    return answer(gr[0]);
  }

  int l1 = 0, r1 = (int)gr[0].size() - 1;
  while (l1 < r1) {
    int mid = (l1 + r1) / 2;
    if (query(std::vector<int>(gr[0].begin(), gr[0].begin() + mid + 1),
              gr[1])) {
      r1 = mid;
    } else {
      l1 = mid + 1;
    }
  }
  int l2 = 0, r2 = (int)gr[1].size() - 1;
  while (l2 < r2) {
    int mid = (l2 + r2) / 2;
    if (query(gr[0],
              std::vector<int>(gr[1].begin(), gr[1].begin() + mid + 1))) {
      r2 = mid;
    } else {
      l2 = mid + 1;
    }
  }

  std::vector<int> ans;
  if (l1 < (int)gr[0].size() - 1) {
    ans.insert(ans.end(), gr[0].begin() + l1 + 1, gr[0].end());
  }
  ans.insert(ans.end(), gr[0].begin(), gr[0].begin() + l1 + 1);
  ans.insert(ans.end(), gr[1].begin() + l2, gr[1].end());
  if (l2 > 0) {
    ans.insert(ans.end(), gr[1].begin(), gr[1].begin() + l2);
  }
  return answer(ans);
}