#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int N;
const int MAXN = 256;
int adj[MAXN][MAXN];
std::vector<int> longest_trip(int _N, int D)
{
N = _N;
// cerr << N << "\n";
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
adj[i][j] = 0;
}
}
for (int i = 0; i < N; ++i) {
adj[i][i] = 1;
for (int j = i + 1; j < N; ++j) {
if (are_connected({i}, {j})) {
adj[i][j] = 1;
adj[j][i] = 1;
}
}
}
if (N <= 5) {
vector<int> res, ord(N);
iota(begin(ord), end(ord), 0);
do {
vector<int> now{ord[0]};
for (int j = 1; j < N; ++j) {
if (!adj[ord[j - 1]][ord[j]]) {
break;
}
now.push_back(ord[j]);
}
if (res.size() < now.size()) res = now;
} while (next_permutation(begin(ord), end(ord)));
return res;
}
deque<int> dq1, dq2;
dq1.push_back({0});
for (int i = 1; i < N; ++i) {
if (adj[dq1.front()][i]) {
dq1.push_front(i);
} else if (adj[dq1.back()][i]){
dq1.push_back(i);
} else {
dq2.push_back(i);
}
}
if (dq1.size() < dq2.size()) swap(dq1, dq2);
// for (auto& u : dq1) {
// cout << u << " ";
// }
// cout << "\n";
// for (auto& u : dq2) {
// cout << u << " ";
// }
// cout << "\n";
while (dq2.size()) {
int v = dq2.front();
dq2.pop_front();
// cout << v << "\n";
if (adj[dq1.front()][v]) {
dq1.push_front(v);
} else if (adj[dq1.back()][v]) {
dq1.push_back(v);
} else {
assert(adj[dq1.front()][dq1.back()]);
// for (auto& u : dq1) {
// cout << u << " ";
// }
// cout << "\n";
for (int j = 0; j < (int)dq1.size(); ++j) {
if (adj[dq1[j]][v]) {
// cout << j << " => ";
deque<int> nw;
for (int k = 0; k <= j; ++k) {
nw.push_back(dq1[k]);
}
for (int k = dq1.size() - 1; k > j; --k) {
nw.push_front(dq1[k]);
}
nw.push_back(v);
dq1 = nw;
// for (auto& u : dq1) {
// cout << u << " ";
// }
// cout << "\n";
break;
}
}
}
}
vector<int> res;
while (dq1.size()) {
res.push_back(dq1.front());
dq1.pop_front();
}
// cerr << res.size() << "\n";
return res;
}
