#include <bits/stdc++.h>
#include <random>
#include "longesttrip.h"
#ifndef LOCAL
#define cerr if (false) cerr
#endif
using namespace std;
std::vector<int> longest_trip(int N, int D)
{
mt19937 mt(123213);
vector<int> pi;
pi.resize(N);
iota(pi.begin(),pi.end(),0);
shuffle(pi.begin(),pi.end(),mt);
auto isline = [&](vector<int> a) {
for (auto& x : a) x = pi[x];
#ifdef LOCAL
for (int i = 1; i < a.size(); ++i) {
assert(are_connected({a[i-1]}, {a[i]}));
}
#endif
return a;
};
auto check = [&](vector<int> a, vector<int> b) {
for (auto& x : a) x = pi[x];
for (auto& x : b) x = pi[x];
return are_connected(a,b);
};
vector<int> path{0};
vector<vector<int>> cliques;
for (int i = 1; i < N; ++i) {
cliques.push_back({i});
}
optional<vector<int>> disj;
while (!cliques.empty()) {
shuffle(cliques.begin(),cliques.end(),mt);
auto cand = cliques.back(); cliques.pop_back();
cerr << path.back() << " : ";
for (auto x : cand) cerr << x << ", ";
cerr << "\n";
if (check({path.back()}, cand)) {
int lo = 0, hi = cand.size();
while (hi-lo > 1) {
int mid = (lo+hi)/2;
vector<int> v;
for (int i = lo; i < mid; ++i) {
v.push_back(cand[i]);
}
if (check({path.back()}, v)) {
hi = mid;
} else {
lo = mid;
}
}
swap(cand[0],cand[lo]);
path.insert(path.end(),cand.begin(),cand.end());
if (disj) {
cliques.push_back(*disj);
disj.reset();
}
} else {
if (disj) {
auto& v = disj.value();
v.insert(v.end(),cand.begin(),cand.end());
} else {
disj = cand;
}
}
}
if (!disj) {
return isline(path);
}
vector<int> rest = *disj;
if (!check(path, rest)) {
return isline(path.size() >= rest.size() ? path : rest);
}
if (check({path.front()},rest)) {
reverse(path.begin(),path.end());
} else {
int lo = 0, hi = path.size();
while (hi-lo > 1) {
int mid = (lo+hi)/2;
vector<int> v;
for (int i = mid; i < hi; ++i) {
v.push_back(path[i]);
}
if (check(v, rest)) {
lo = mid;
} else {
hi = mid;
}
}
rotate(path.begin(),path.begin()+hi,path.end());
}
int lo = 0, hi = rest.size();
while (hi-lo > 1) {
int mid = (lo+hi)/2;
vector<int> v;
for (int i = lo; i < mid; ++i) {
v.push_back(rest[i]);
}
if (check({path.back()}, v)) {
hi = mid;
} else {
lo = mid;
}
}
rotate(rest.begin(),rest.begin()+lo,rest.end());
path.insert(path.end(),rest.begin(),rest.end());
return isline(path);
}
