#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 260;
vector < int > adj[maxn];
int used[maxn], edge[maxn][maxn];
int n;
void dfs(int v, int c)
{
used[v] = c;
for (int u : adj[v])
{
if (!used[u])
dfs(u, c);
}
}
int deg[maxn];
vector<int> longest_trip(int N, int D)
{
n = N;
if (n == 0)
return {};
if (D == 3)
{
vector < int > r;
for (int i = 0; i < N; i ++)
r.push_back(i);
return r;
}
for (int i = 0; i < N; i ++)
for (int j = 0; j < N; j ++)
{
edge[i][j] = edge[j][i] = 0;
}
for (int i = 0; i < N; i ++)
used[i] = 0, deg[i] = 0;
for (int i = 0; i < N; i ++)
for (int j = i + 1; j < N; j ++)
{
vector < int > a, b;
a.push_back(i);
b.push_back(j);
if (are_connected(a, b))
{
adj[i].push_back(j);
adj[j].push_back(i);
edge[i][j] = 1;
edge[j][i] = 1;
deg[i] ++;
deg[j] ++;
}
}
int cp = 0;
for (int i = 0; i < N; i ++)
{
if (!used[i])
dfs(i, ++ cp);
}
if (cp == 2)
{
vector < int > a, b;
for (int i = 0; i < N; i ++)
if (used[i] == 1)
a.push_back(i);
else
b.push_back(i);
if (a.size() > b.size())
return a;
return b;
}
vector < int > res;
int tk = 0;
while(tk < N && deg[tk] != 1)
tk ++;
if (tk == N)
tk = 0;
for (int step = 0; step < N; step ++)
{
res.push_back(tk);
int nxt = -1;
for (int u = 0; u < N; u ++)
{
if (edge[tk][u])
{
deg[u] --;
if (deg[u] == 1 || nxt == -1)
nxt = u;
deg[tk] --;
edge[tk][u] = edge[u][tk] = 0;
}
}
tk = nxt;
}
return res;
}
