#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using dll = deque <ll>;
using vi = vector <int>;
const ll MAXN = 256+16;
vll adj[MAXN];
bool mat[MAXN][MAXN];
ll tvis[MAXN];
ll timer = 1;
void dfs (ll u, ll timer, ll &c) {
if (tvis[u] == timer) return;
tvis[u] = timer;
c++;
for (ll v : adj[u]) {
dfs(v, timer, c);
}
}
vi longest_trip (int n, int d) {
timer++;
fill(adj, adj+n+5, vll({}));
for (ll u = 0; u < n; u++) {
for (ll v = 0; v < n; v++) {
mat[u][v] = false;
}
}
for (ll u = 0; u < n; u++) {
mat[u][u] = false;
for (ll v = u+1; v < n; v++) {
if (are_connected(vi({ int(u) }), vi({ int(v) }))) {
adj[u].push_back(v);
adj[v].push_back(u);
mat[u][v] = true;
mat[v][u] = true;
} else {
mat[u][v] = false;
mat[v][u] = false;
}
}
}
ll c = 0;
dfs(0, timer, c);
if (c == n) {
vi ans;
ans.push_back(0);
ll op1 = 1, op2 = 2;
while (max(op1, op2) < n) {
if (mat[ans.back()][op1]) {
ans.push_back(op1);
op1 = max(op1, op2)+1;
} else if (mat[ans.back()][op2]) {
ans.push_back(op2);
op2 = max(op1, op2)+1;
} else assert(false);
}
ans.push_back(min(op1, op2));
return ans;
} else {
if (2*c > n) { // timer is may
vi ans;
for (ll u = 0; u < n; u++) {
if (tvis[u] == timer) {
if(ans.size()) assert(mat[u][ans.back()]);
ans.push_back(u);
}
}
return ans;
} else { // timer isnt may
vi ans;
for (ll u = 0; u < n; u++) {
if (tvis[u] != timer) {
if(ans.size()) assert(mat[u][ans.back()]);
ans.push_back(u);
}
}
return ans;
}
}
}
