#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 > construct(int v)
{
used[v] = 1;
vector < int > viable;
for (int u : adj[v])
if (!used[u])
viable.push_back(u);
if (viable.size() == 0)
{
vector < int > cur;
cur.push_back(v);
return cur;
}
if (viable.size() == 1)
{
vector < int > res = construct(viable[0]);
res.push_back(v);
return res;
}
vector < int > r1 = construct(viable[0]), r2;
for (int u : viable)
{
if (used[u] == 0)
r2 = construct(u);
}
vector < int > res = r1;
if (r2.size() > res.size())
res = r2;
res.push_back(v);
return res;
}
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 ++)
adj[i].clear();
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);
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;
}
for (int i = 0; i < N; i ++)
used[i] = 0;
vector < int > res = construct(0);
return res;
}
