#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 256;
vector<int> nei[M];
int find(vector<int> v,vector<int> v1)
{
map<int,int> ind;
for (int i=0;i<v1.size();i++) ind[v1[i]]=i;
int ans=v1.size()-1;
for (int u:v)
for (int i:nei[u])
if (ind.count(i))
ans=min(ans,ind[i]);
return ans;
}
vector<int> cc;
bool vis[M];
void dfs(int u)
{
vis[u]=1;cc.push_back(u);
for (int i:nei[u])
if (!vis[i]) dfs(i);
}
vector<int> longest_trip(int n, int D)
{
cc.clear();
for (int i=0;i<n;i++)
nei[i].clear(),vis[i]=0;
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
if (are_connected({i},{j}))
nei[i].push_back(j),nei[j].push_back(i);
dfs(0);
if (cc.size()<n)
{
if (cc.size()*2>=n)
return cc;
cc.clear();
for (int i=0;i<n;i++)
if (!vis[i]) cc.push_back(i);
return cc;
}
for (int i=1;i<n;i++) vis[i]=0;
vector<int> cur={0};
while (cur.size()<n)
{
vector<int> v;
for (int i=0;i<n;i++)
if (!vis[i])
v.push_back(i);
int x=v[find(cur,v)];
vis[x]=1;
int a=find({x},cur);
reverse(cur.begin(),cur.end());
int b=find({x},cur);
if (a<b)
{
reverse(cur.begin(),cur.end());
b=a;
}
vector<int> nw={x};
for (int i=b;i<cur.size();i++)
nw.push_back(cur[i]);
for (int i=0;i<b;i++)
nw.push_back(cur[i]);
cur=nw;
}
return cur;
}
