#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N, int D) {
vector<int> v1, v2;
int i;
vector<int> rems;
for (i = 1; i < N; i++) rems.push_back(i);
v1.push_back(0);
while (rems.size()) {
int x, y;
if (rems.size() == 1) {
x = rems.back();
rems.pop_back();
if (v2.empty()) {
int a = v1.back();
if (are_connected({ a }, { x })) v1.push_back(x);
else v2.push_back(x);
}
else {
int a = v1.back();
int b = v2.back();
auto c1 = are_connected({ x }, { a });
auto c2 = are_connected({ x }, { b });
if (c1 && c2) {
v1.push_back(x);
while (v2.size()) v1.push_back(v2.back()), v2.pop_back();
}
else if (c1) v1.push_back(x);
else if (c2) v2.push_back(x);
else assert(0);
}
}
else {
x = rems.back();
rems.pop_back();
y = rems.back();
rems.pop_back();
if (v2.empty()) {
int a = v1.back();
auto ax = are_connected({ a }, { x });
auto ay = are_connected({ a }, { y });
auto xy = are_connected({ x }, { y });
if (ax && xy) {
v1.push_back(x);
v1.push_back(y);
}
else if (ay && xy) {
v1.push_back(y);
v1.push_back(x);
}
else if (ax) {
v1.push_back(x);
v2.push_back(y);
}
else if (ay) {
v1.push_back(y);
v2.push_back(x);
}
else {
assert(xy);
v2.push_back(x);
v2.push_back(y);
}
}
else {
int a = v1.back();
int b = v2.back();
if (are_connected({ x }, { y })) {
if (are_connected({ a }, { x })) {
if (are_connected({ b }, { y })) {
v1.push_back(x);
v1.push_back(y);
while (v2.size()) v1.push_back(v2.back()), v2.pop_back();
}
else {
v1.push_back(x);
v1.push_back(y);
}
}
else {
if (are_connected({ a }, { y })) {
v1.push_back(y);
v1.push_back(x);
while (v2.size()) v1.push_back(v2.back()), v2.pop_back();
}
else {
v2.push_back(x);
v2.push_back(y);
}
}
}
else {
if (are_connected({ a }, { x })) {
if (are_connected({ b }, { y })) {
v1.push_back(x);
v2.push_back(y);
}
else {
v1.push_back(y);
v2.push_back(x);
}
}
else {
v1.push_back(y);
v2.push_back(x);
}
}
}
}
if (v1.size() && v2.size()) assert(!are_connected({ v1.back() }, { v2.back() }));
}
for (i = 1; i < v1.size(); i++) {
assert(are_connected({ v1[i - 1] }, { v1[i] }));
}
for (i = 1; i < v2.size(); i++) {
assert(are_connected({ v2[i - 1] }, { v2[i] }));
}
if (v2.empty()) return v1;
if (!are_connected(v1, v2)) {
if (v1.size() < v2.size()) return v2;
else return v1;
}
int M, K;
M = v1.size();
K = v2.size();
int l, r;
l = -1;
r = M - 1;
while (r - l > 1) {
int m = l + r >> 1;
vector<int> prf = v1;
prf.resize(m + 1);
if (are_connected(prf, v2)) r = m;
else l = m;
}
int u = r;
vector<int> v1prf = v1;
v1prf.resize(r + 1);
assert(are_connected(v1prf, v2));
l = -1;
r = K - 1;
while (r - l > 1) {
int m = l + r >> 1;
vector<int> prf = v2;
prf.resize(m + 1);
if (are_connected(v1prf, prf)) r = m;
else l = m;
}
int v = r;
assert(are_connected({ v1[u] }, { v2[v] }));
vector<int> allv;
int st = (u + 1) % M;
for (i = 0; i < M; i++) {
allv.push_back(v1[st]);
st = (st + 1) % M;
}
st = v;
for (i = 0; i < K; i++) {
allv.push_back(v2[st]);
st = (st + 1) % K;
}
return allv;
}
