#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vec;
#define q are_connected
#define pb push_back
vec a, b; int p[256];
void app() {
	for (int i : b) a. pb(i);
	b. clear();
}
vec longest_trip(int n, int d) {
	srand(114);
	for (int i=0; i<n; i++) p[i] = i;
	random_shuffle (p, p+n);
	a = vec {p[0]}, b = vec {p[1]};
	bool f = 0;
	for (int _=2; _<n; _++) {
		int i = p[_];
		if (q({a. back()}, {i})) a. pb(i), f = 0;
		else if (f || q({b. back()}, {i})) b. pb(i), f = 1;
		else reverse (b. begin(), b. end()), app(), b. pb(i);
	}
	if (b. empty()) return a;
	if (! q(a, b)) return a. size() > b. size() ? a : b;
	if (! f && q({a. back()}, {b. back()})) return reverse (b. begin(), b. end()), app(), a;
	if (q({a. back()}, b)) {
		int l = 0, r = b. size() - 2;
		while (l < r) {
			int mid = l + r >> 1;
			if (q({a. back()}, vec (b. begin(), b. begin() + mid + 1))) r = mid;
			else l = mid + 1;
		} return rotate (b. begin(), b. begin() + r, b. end()), app(), a;
	} else {
		int l = 0, r = a. size() - 2;
		while (l < r) {
			int mid = l + r >> 1;
			if (q(vec (a. begin(), a. begin() + mid + 1), b)) r = mid;
			else l = mid + 1;
		} r ? rotate (a. begin(), a. begin() + r + 1, a. end()), void () : reverse (a. begin(), a. end());
		l = 0, r = b. size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (q({a. back()}, vec (b. begin(), b. begin() + mid + 1))) r = mid;
			else l = mid + 1;
		} return rotate (b. begin(), b. begin() + r, b. end()), app(), a;
	}
}