// Source: https://usaco.guide/general/io

#include "longesttrip.h"
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()

using namespace std;

map<pair<vector<int>, vector<int>>, bool> dp;

bool connected(vector<int> a, vector<int> b) {
	if (!dp.count({a, b})) {
		dp[{a, b}] = are_connected(a, b);
	}

	return dp[{a, b}];
}

vector<int> longest_trip(int N, int D) {
	dp.clear();

	vector<int> chain1, chain2, chain3;

	vector<int> a, b, newa, newb;

	vector<int> trust;

	for (int i = 0; i < N; i++) {
		trust.push_back(i);
	}

	// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
	// shuffle(trust.begin(), trust.end(), rng);

	random_shuffle(all(trust));

	chain1.push_back(trust[0]), chain2.push_back(trust[1]);

	for (int i = 2; i + 1 < N; i += 2) {
		a.clear(); a.push_back(chain1.back());
		b.clear(); b.push_back(chain2.back());
		newa.clear(); newa.push_back(trust[i]);
		newb.clear(); newb.push_back(trust[i + 1]);

		if (connected(newa, newb)) {
			if (connected(a, newa)) {
				chain1.push_back(newa.back()); chain1.push_back(newb.back());
			} else if (connected(b, newa)) {
				chain2.push_back(newa.back()); chain2.push_back(newb.back());
			} else {
				for (int i = sz(chain2) - 1; i >= 0; i--) {
					chain1.push_back(chain2[i]);
				}

				chain2.clear(); chain2.push_back(newa[0]), chain2.push_back(newb[0]);
			}
		} else if (connected(a, newa)) {
			chain1.push_back(newa[0]);

			if (connected(b, newa)) {
				for (int i = sz(chain2) - 1; i >= 0; i--) {
					chain1.push_back(chain2[i]);
				}

				chain2.clear(); chain2.push_back(newb[0]);
			} else {
				chain2.push_back(newb[0]);
			}
		} else {
			chain1.push_back(newb[0]);

			if (connected(b, newb)) {
				for(int i = sz(chain2) - 1; i >= 0; i--) {
					chain1.push_back(chain2[i]);
				}

				chain2.clear(); chain2.push_back(newa[0]);
			} else {
				chain2.push_back(newa[0]);
			}
		}
	}

	if (N % 2) {
		a.clear(); a.push_back(chain1.back());
		b.clear(); b.push_back(chain2.back());
		newa.clear(); newa.push_back(trust[N - 1]);

		if (connected(a, newa)) {
			chain1.push_back(newa[0]);
		} else if (connected(b, newa)) {
			chain2.push_back(newa[0]);
		} else {
			for (int i = sz(chain2) - 1; i >= 0; i--) {
				chain1.push_back(chain2[i]);
			}

			chain2.clear(); chain2.push_back(newa[0]);
		}
	}

	if (!connected(chain1, chain2)) {
		if (sz(chain1) > sz(chain2)) {
			return chain1;
		} else {
			return chain2;
		}
	}

	a.clear(); a.push_back(chain1.back());
	b.clear(); b.push_back(chain2.back());

	if (connected(a, b)) {
		// entire thing
		for (int i = 0; i < sz(chain2); i++) {
			chain1.push_back(chain2[i]);
		}

		return chain1;
	}

	a.clear(); a.push_back(chain1.back());
	b.clear(); b.push_back(chain2[0]);

	if (connected(a, b)) {
		for (int i : chain2) {
			chain1.push_back(i);
		}

		return chain1;
	}

	a.clear(), a.push_back(chain1[0]);
	b.clear(), b.push_back(chain2.back());

	if (connected(a, b)) {
		for (int i : chain1) {
			chain2.push_back(i);
		}
		
		return chain2;
	}

	// I FUCKING HATE THESE PROBLEMS ADSLKFJALSDKJFSHDJI''DS;INUOSJOERFEEWFAJNEIJ9IIQ2IW2O-p-12323948893vn [WUR89R1KJASHILUA EIFJFLJKJKDKLKKLJ;KL;KL;LKKL;J]
	a.clear(), a.push_back(chain1[0]);
	b.clear(), b.push_back(chain2[0]);

	if(connected(a, b)) {
		chain3.clear();

		for (int i = sz(chain1) - 1; i >= 0; i--) {
			chain3.push_back(chain1[i]);
		}

		for (int i = 0; i < sz(chain2); i++) {
			chain3.push_back(chain2[i]);
		}

		return chain3;
	}

	int l = 0, r = sz(chain2);

	while (l < r) {
		int m = l + (r - l) / 2;

		if (l == m) {
			break;
		}

		chain3.clear();

		for (int i = l; i < m; i++) {
			chain3.push_back(chain2[i]);
		}

		if (sz(chain3) && connected(chain1, chain2)) {
			r = m;
		} else {
			l = m;
		}
	}

	int fuck = r - 1;
	l = 0, r = sz(chain1);
	b.clear(), b.push_back(chain2[fuck]);
	int last_mid = l + (r - l) / 2;
	while (l < r) {
		int m = l + (r - l) / 2; last_mid = m;

		if (l == m) {
			break;
		}

		chain3.clear();

		for (int i = l; i < m; i++) {
			chain3.push_back(chain1[i]);
		}

		if (sz(chain3) > 0 && connected(b, chain3)) {
			r = m;
		} else {
			l = m;
		}
	}

	a.clear(), a.push_back(chain1[last_mid]);
	chain3.clear();

	for (int i = r; i < sz(chain1); i++) {
		chain3.push_back(chain1[i]);
	}

	for (int i = 0; i < r; i++) {
		chain3.push_back(chain1[i]);
	}

	for (int i = fuck; i < sz(chain2); i++) {
		chain3.push_back(chain2[i]);
	}

	for (int i = 0; i < fuck; i++) {
		chain3.push_back(chain2[i]);
	}

	return chain3;
}