#include "longesttrip.h"
#include <iostream>
#include <algorithm>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
vector<int> gph[404];
bool chc[404];
bool vst[404];
void dfs(int x)
{
vst[x] = true;
for(auto y : gph[x]) if(chc[y] && !vst[y]) dfs(y);
}
vector<vector<int>> cmpn(int N)
{
fill(vst, vst + N, false);
for(int i = 0; i < N; ++i) if(chc[i]) { dfs(i); break; }
vector<int> r1, r2;
for(int i = 0; i < N; ++i) if(chc[i])
{
if(vst[i]) r1.push_back(i);
else r2.push_back(i);
}
if(r2.empty()) return {r1};
else return {r1, r2};
}
vector<int> longest_trip(int N, int d)
{
for(int i = 0; i < N; ++i) gph[i].clear();
fill(chc, chc + N, true);
for(int i = 0; i < N; ++i)
{
for(int j = i + 1; j < N; ++j)
{
if(are_connected(vector<int>{i}, vector<int>{j}))
{
gph[i].push_back(j);
gph[j].push_back(i);
}
}
}
auto V = cmpn(N);
if(V.size() == 2)
{
if(V[0].size() < V[1].size()) swap(V[0], V[1]);
return V[0];
}
int x;
for(int i = 0; i < N; ++i)
{
chc[i] = false;
if(cmpn(N).size() == 1)
{
x = i;
break;
}
chc[i] = true;
}
vector<int> ret{x};
for(int k = 1; k < N; ++k)
{
for(auto i : gph[x]) if(chc[i])
{
chc[i] = false;
if(cmpn(N).size() == 1)
{
x = i;
ret.push_back(x);
break;
}
chc[i] = true;
}
}
return ret;
}
