#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ALL(a) a.begin(), a.end()
bool check(int v, int u) {
return are_connected({v}, {u});
}
pair<vector<int>, vector<int>> two_path(int N, int D) {
deque<int> A, B;
A = {0};
B = {1};
for (int x=2; x<N; x++) {
int v = A.back();
int u = B.back();
if (check(x, v)) A.pb(x);
else B.pb(x);
}
vector<int> p, q;
while (!A.empty()) {
p.pb(A.back());
A.pop_back();
}
while (!B.empty()) {
q.pb(B.back());
B.pop_back();
}
return make_pair(p, q);
}
std::vector<int> longest_trip(int N, int D) {
auto [A, B] = two_path(N, D);
if (A.size() < B.size()) swap(A, B);
if (B.empty()) return A;
{
int v = A[0], u = A.back();
int x = B[0], y = B.back();
if (check(u, x)) {
for (int p : B) A.pb(p);
return A;
}
if (check(v, x)) {
reverse(ALL(A));
for (int p : B) A.pb(p);
return A;
}
if (check(v, y)) {
reverse(ALL(A));
reverse(ALL(B));
for (int p : B) A.pb(p);
return A;
}
if (check(u, y)) {
reverse(ALL(B));
for (int p : B) A.pb(p);
return A;
}
// if (v!=u) assert(check(v, u));
// if (x!=y) assert(check(x, y));
}
if (!are_connected(A, B)) return A;
int j = B.size();
{
vector<int> vec = B;
for (int k=128; 1<=k; k>>=1) {
if (k < vec.size()) {
vector<int> save;
for (int _=0; _<k; _++) {
save.pb(vec.back());
vec.pop_back();
}
reverse(ALL(save));
if (are_connected(vec, A)) j -= k;
else for (int p : save) vec.pb(p);
}
}
}
assert(0<j);
j--;
int i = A.size();
{
vector<int> vec = A;
for (int k=128; 1<=k; k>>=1) {
if (k < vec.size()) {
vector<int> save;
for (int _=0; _<k; _++) {
save.pb(vec.back());
vec.pop_back();
}
reverse(ALL(save));
if (are_connected(vec, {B[j]})) i -= k;
else for (int p : save) vec.pb(p);
}
}
}
assert(0<i);
i--;
vector<int> L{A[i]};
int k = (i+1) % A.size();
while (k != i) {
L.pb(A[k]);
k = (k+1) % A.size();
}
reverse(ALL(L));
vector<int> R{B[j]};
k = (j+1) % B.size();
while (k != j) {
R.pb(B[k]);
k = (k+1) % B.size();
}
for (int p : R) L.pb(p);
return L;
}
