#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(114514);
	for (int i=0; i<n; i++)
		p[i] = i;
	random_shuffle (p, p+n);
	a = vec {p[0]}, b = vec {};
	for (int i=1; i<n; i++)
		if (q({a. back()}, {p[i]})) {
			a. pb(p[i]);
			if (! b. empty() && q({b. back()}, {p[i]}))
				reverse (b. begin(), b. end()), app();
		} else b. pb(p[i]);
	if (b. empty()) return a;
	if (! q(a, b)) return a. size() > b. size() ? a : b;
	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;
	}
}