#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
vector<int> longest_trip(int n, int d) {
	vector<int> l1, l2, l3, a, b, c;
	vector<int> idfk;
	for(int i = 0; i < n; i++) idfk.push_back(i);
	random_shuffle(idfk.begin(), idfk.end());
	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(are_connected(a, b)) {
			for(int j = l2.size() - 1; j >= 0; j--) l1.push_back(l2[j]);
			l2 = l3;
		} else if(are_connected(a, c)) {
			for(int j = l3.size() - 1; j >= 0; j--) l1.push_back(l3[j]);
		} else {
			for(int j = l3.size() - 1; j >= 0; j--) l2.push_back(l3[j]);
		}
	}
	a.clear(), a.push_back(l1.back());
	b.clear(), b.push_back(l2.back());
	if(are_connected(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(are_connected(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(are_connected(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(are_connected(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;
	}
	if(!are_connected(l1, l2)) {
		if(l1.size() > l2.size()) return l1;
		return l2;
	}
	int l = 1, r = l2.size(), mid;
	while(l < r) {
		mid = (l + r) / 2;
		l3.clear();
		for(int i = l; i < mid; i++) l3.push_back(l2[i]);
		if(l3.size() > 0 && are_connected(l1, l3)) r = mid;
		else l = mid + 1;
	}
	int bk = r - 1;
	l = 1, r = l1.size();
	b.clear(), b.push_back(l2[bk]);
	while(l < r) {
		mid = (l + r) / 2;
		l3.clear();
		for(int i = l; i < mid; i++) l3.push_back(l1[i]);
		if(l3.size() > 0 && are_connected(b, l3)) r = mid;
		else l = mid + 1;
	}
	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;
}