#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 256;
vector<int> edge[MAXN];
int dp[MAXN];
void dfs(vector<int> &ccomp, int u) {
ccomp.push_back(u);
for (int v : edge[u]) {
if (dp[v] == -1) {
dp[v] = dp[u] + 1;
dfs(ccomp, v);
}
}
}
vector<int> longest_trip(int N, int D) {
for (int i = 0; i < N; i++) {
edge[i].clear();
dp[i] = -1;
}
bool edge_bool[N][N];
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
if (are_connected({i}, {j})) {
edge[i].push_back(j);
edge[j].push_back(i);
edge_bool[i][j] = edge_bool[j][i] = true;
} else edge_bool[i][j] = edge_bool[j][i] = false;
}
}
for (int i = 0; i < N; i++) sort(edge[i].begin(), edge[i].end());
vector<vector<int>> comp;
for (int i = 0; i < N; i++) {
if (dp[i] != -1) continue;
dp[i] = 0;
vector<int> ccomp;
dfs(ccomp, i);
comp.push_back(ccomp);
}
if (comp.size() > 1) {
if (comp[0].size() < comp[1].size()) swap(comp[0], comp[1]);
return comp[0];
}
int lastfail = -1;
for (int i = 0; i < N-1; i++) {
if (!edge_bool[comp[0][i]][comp[0][i+1]]) {
lastfail = i;
break;
}
}
if (lastfail == -1) return comp[0];
while (comp[0].size() > lastfail+1) comp[0].pop_back();
return comp[0];
}
