#include "longesttrip.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 303;
int n, d;
vector < int > g[maxn];
vector < int > path;
int used[maxn];
int is[maxn][maxn];
void dfs(int beg, vector < int >&curr)
{
used[beg] = 1;
if(curr.size() > path.size())
path = curr;
for (auto nb: g[beg])
{
if(used[nb])continue;
curr.pb(nb);
dfs(nb, curr);
curr.pop_back();
}
}
std::vector<int> longest_trip(int N, int D)
{
n = N;
d = D;
for (int i = 0; i < n; ++ i)
{
for (int j = 0; j < n; ++ j)
is[i][j] = 0;
}
for (int i = 0; i < n; ++ i)
g[i].clear();
for (int i = 0; i < n; ++ i)
{
for (int j = i+1; j < n; ++ j)
{
vector < int > from,to;
from.pb(i);
to.pb(j);
if(are_connected(from, to))
{
g[i].pb(j);
g[j].pb(i);
is[i][j] = 1;
is[j][i] = 1;
}
}
}
path.clear();
for (int st = 0; st < n; ++ st)
{
vector < int > s;
for (int i = 0; i < n; ++ i)
{
s.pb(i);
used[i] = 0;
}
path.pb(st);
used[st] = 1;
int last = st;
while(path.size() < n)
{
while(s.size() && used[s.back()])s.pop_back();
int op = s.back();
if(is[last][op])
{
s.pop_back();
path.pb(op);
}
else
{
while(s.size() && used[s.back()])s.pop_back();
if(s.size() == 0)break;
int mid = s.back();
path.push_back(mid);
path.push_back(op);
s.pop_back();
}
if(path.size() == n)return path;
}
}
return path;
}
