#include <vector>
#include <set>
#include "longesttrip.h"
#include <bitset>
using namespace std;
int const MAXN=256;
vector<int>nei[MAXN]={};
vector<int>ans;
vector<int>cur;
bitset<MAXN>vis;
int root=0;
vector<int> dfs(int u)
{
vis[u]=1;
vector<int>mx,mx1;
for (auto i:nei[u])
{
if (vis[i])
continue;
vector<int>z=dfs(i);
if (z.size()>mx.size())
{
mx1=mx;
mx=z;
}
else if (z.size()>mx1.size())
mx1=z;
}
if (u==root)
{
vector<int>f=mx;
f.push_back(u);
for (auto i:mx1)
f.push_back(i);
if (f.size()>ans.size())
ans=f;
return f;
}
mx.push_back(u);
return mx;
}
vector<int> longest_trip(int N, int D)
{
ans.clear();
cur.clear();
for (int i=0;i<N;i++)
nei[i].clear();
vector<int>x,y;
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);
}
for (int i=0;i<N;i++)
{
if (!vis[i])
{
root=i;
dfs(i);
}
}
return ans;
}
