#include "longesttrip.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
// cope counter = 2254
#pragma GCC optimize("O3,unroll-loops,Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

map<pair<vector<int>, vector<int>>, bool> kms;

bool qry(vector<int> a, vector<int> b) {
	if(!kms.contains(mp(a, b))) kms[mp(a, b)] = are_connected(a, b);
	return kms[mp(a, b)];
}

vector<int> longest_trip(int n, int D) {
	kms.clear();
	vector<int> l1, l2, l3, a, b, c, d;
	vector<int> idfk;
	for(int i = 0; i < n; i++) idfk.push_back(i);
	mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
	shuffle(idfk.begin(), idfk.end(), rng);
	l1.push_back(idfk[0]), l2.push_back(idfk[1]);
	for(int i = 2; i + 1 < n; i += 2) {
		a.clear(), a.push_back(l1.back());
		b.clear(), b.push_back(l2.back());
		c.clear(), c.push_back(idfk[i]);
		d.clear(), d.push_back(idfk[i + 1]);
		if(qry(c, d)) {
			if(qry(a, c)) l1.push_back(c[0]), l1.push_back(d[0]);
			else if(qry(b, c)) l2.push_back(c[0]), l2.push_back(d[0]);
			else {
				for(int i = l2.size() - 1; i >= 0; i--) l1.push_back(l2[i]);
				l2.clear();
				l2.push_back(c[0]), l2.push_back(d[0]);
			}
		} else if(qry(a, c)) {
			l1.push_back(c[0]);
			if(qry(b, c)) {
				for(int i = l2.size() - 1; i >= 0; i--) l1.push_back(l2[i]);
				l2.clear();
				l2.push_back(d[0]);
			} else {
				l2.push_back(d[0]);
			}
		} else {
			l1.push_back(d[0]);
			if(qry(b, d)) {
				for(int i = l2.size() - 1; i >= 0; i--) l1.push_back(l2[i]);
				l2.clear();
				l2.push_back(c[0]);
			} else {
				l2.push_back(c[0]);
			}
		}
	}
	if(n % 2) {
		a.clear(), a.push_back(l1.back());
		b.clear(), b.push_back(l2.back());
		c.clear(), c.push_back(idfk[n - 1]);
		if(qry(a, c)) l1.push_back(c[0]);
		else if(qry(b, c)) l2.push_back(c[0]);
		else {
			for(int i = l2.size() - 1; i >= 0; i--) l1.push_back(l2[i]);
			l2.clear();
			l2.push_back(c[0]);
		}
	}
	if(!qry(l1, l2)) {
		if(l1.size() > l2.size()) return l1;
		return l2;
	}
	a.clear(), a.push_back(l1.back());
	b.clear(), b.push_back(l2.back());
	if(qry(a, b)) {
		for(int i = l2.size() - 1; i >= 0; i--) l1.push_back(l2[i]);
		return l1;
	}
	a.clear(), a.push_back(l1.back());
	b.clear(), b.push_back(l2[0]);
	if(qry(a, b)) {
		for(int i = 0; i < l2.size(); i++) l1.push_back(l2[i]);
		return l1;
	}
	a.clear(), a.push_back(l1[0]);
	b.clear(), b.push_back(l2.back());
	if(qry(a, b)) {
		for(int i = 0; i < l1.size(); i++) l2.push_back(l1[i]);
		return l2;
	}
	a.clear(), a.push_back(l1[0]);
	b.clear(), b.push_back(l2[0]);
	if(qry(a, b)) {
		l3.clear();
		for(int i = l1.size() - 1; i >= 0; i--) l3.push_back(l1[i]);
		for(int i = 0; i < l2.size(); i++) l3.push_back(l2[i]);
		return l3;
	}
	int l = 0, r = l2.size(), mid;
	while(l < r) {
		mid = (l + r) / 2;
		if(l == mid) break;
		l3.clear();
		for(int i = l; i < mid; i++) l3.push_back(l2[i]);
		if(l3.size() > 0 && qry(l1, l3)) r = mid;
		else l = mid;
	}
	int bk = r - 1;
	l = 0, r = l1.size();
	b.clear(), b.push_back(l2[bk]);
	while(l < r) {
		mid = (l + r) / 2;
		if(l == mid) break;
		l3.clear();
		for(int i = l; i < mid; i++) l3.push_back(l1[i]);
		if(l3.size() > 0 && qry(b, l3)) r = mid;
		else l = mid;
	}
	a.clear(), a.push_back(l1[mid]);
	l3.clear();
	for(int i = r; i < l1.size(); i++) l3.push_back(l1[i]);
	for(int i = 0; i < r; i++) l3.push_back(l1[i]);
	for(int i = bk; i < l2.size(); i++) l3.push_back(l2[i]);
	for(int i = 0; i < bk; i++) l3.push_back(l2[i]);
	return l3;
}