#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;
void app() {
	for (int i : b) a. pb(i);
	b. clear();
}
vec longest_trip(int n, int d) {
	a = vec {0}, b = vec {};
	for (int i=1; i<n; i++)
		if (q({a. back()}, {i})) {
			a. pb(i);
			if (! b. empty() && q({b. back()}, {i}))
				reverse (b. begin(), b. end()), app();
		} else b. pb(i);
	if (b. empty()) return a;
	if (! q(a, b)) return a. size() > b. size() ? a : b;
	if (q({a. back()}, {* b. begin()})) return app(), a;
	if (q({a. back()}, b)) {
		int l = 1, r = b. size() - 2;
		while (l < r) {
			int mid = l + r >> 1;
			if (q({a. back()}, vec (b. begin() + 1, b. begin() + mid + 1))) r = mid;
			else l = mid + 1;
		} return rotate (b. begin(), b. begin() + r, b. end()), app(), a;
	} else {
		if (q({* a. begin()}, b)) return reverse (a. begin(), a. end()), app(), a;
		int l = 1, r = a. size() - 2;
		while (l < r) {
			int mid = l + r >> 1;
			if (q(vec (a. begin() + 1, a. begin() + mid + 1), b)) r = mid;
			else l = mid + 1;
		} return rotate (a. begin(), a. begin() + r + 1, a. end()), app(), a;
	}
}