#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int dicho(vector<int> a, vector<int> b) {
if((int)a.size() == 1) return a[0];
vector<int> cut[2];
int cnt = 0;
for(int i : a) {
cnt++;
cut[cnt % 2].push_back(i);
}
if(are_connected(cut[1], b)) return dicho(cut[1], b);
return dicho(cut[0], b);
}
bool seeded = false;
mt19937 rng(42);
vector<int> longest_trip(int N, int D) {
vector<int> a, b;
if(!seeded) rng.seed(N ^ ((D * 165) + 42));
seeded = true;
vector<int> perm(N);
for(int i = 0; i < N; i++)
perm[i] = i;
shuffle(perm.begin(), perm.end(), rng);
a.push_back(perm[0]);
for(int i = 1; i < N; i++) {
if(b.empty()) {
if(rng() % 2 == 0) reverse(a.begin(), a.end());
if(are_connected({a.back()}, {perm[i]}))
a.push_back(perm[i]);
else
b.push_back(perm[i]);
} else {
if(rng() % 2 == 0) swap(a, b);
if(are_connected({a.back()}, {perm[i]})) {
a.push_back(perm[i]);
if(are_connected({a.back()}, {b.back()})) {
while(!b.empty()) {
a.push_back(b.back());
b.pop_back();
}
}
} else {
b.push_back(perm[i]);
}
}
}
if(b.empty()) return a;
if((int)a.size() == 1 || are_connected({a[0]}, {a.back()})) {
if((int)b.size() == 1 || are_connected({b[0]}, {b.back()})) {
if(are_connected(a, b)) {
int x = dicho(a, b);
int y = dicho(b, {x});
deque<int> A, B;
for(int i : a) A.push_back(i);
for(int i : b) B.push_back(i);
while(A.back() != x) {
A.push_back(A[0]);
A.pop_front();
}
while(B[0] != y) {
B.push_back(B[0]);
B.pop_front();
}
vector<int> ans;
for(int i : A) ans.push_back(i);
for(int i : B) ans.push_back(i);
return ans;
} else {
if(a.size() < b.size()) swap(a, b);
return a;
}
} else {
swap(a, b);
}
}
if(are_connected({a[0]}, {b.back()})) {
for(int i : a) b.push_back(i);
return b;
} else {
while(!b.empty()) {
a.push_back(b.back());
b.pop_back();
}
return a;
}
}
