#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

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;
	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 < n; i++) {
		l3.clear();
		l3.push_back(idfk[i]);
		a.clear(), a.push_back(l1.back());
		b.clear(), b.push_back(l2.back());
		c.clear(), c.push_back(l3.back());
		if(qry(a, b)) {
			for(int j = l2.size() - 1; j >= 0; j--) l1.push_back(l2[j]);
			swap(l2, l3);
		} else if(qry(a, c)) {
			l1.push_back(l3[0]);
		} else {
			l2.push_back(l3[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;
}