#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
const int nmax = 256;
int n;
std::vector<int> G[nmax + 5];
int d[nmax + 5];
bool sel[nmax + 5];
int t[nmax + 5];
int split, l1, l2;
int find_next_go(int nod)
{
for(auto it : G[nod])
{
if(!sel[it])
{
return it;
}
}
return -1;
}
void dfs(int nod)
{
sel[nod] = true;
int son = find_next_go(nod);
int nr_sons = 0;
while(son!=-1)
{
t[son] = nod;
dfs(son);
son = find_next_go(nod);
++nr_sons;
}
if(nr_sons==2)
{
split = nod;
}
if(!nr_sons)
{
if(l1==-1)
{
l1 = nod;
}
else
{
l2 = nod;
}
}
}
std::vector<int> solve_component(int root)
{
dfs(root);
vector<int> r;
if(l2==-1)
{
int nod = l1;
r.push_back(l1);
while(nod!=root)
{
nod = t[nod];
r.push_back(nod);
}
return r;
}
vector<int> a,b;
bool ok = false;
for(auto it : G[l1])
{
if(it==root)
{
ok = true;
}
}
if(!ok)
{
swap(l1,l2);
}
int nod = l1;
while(nod!=split)
{
a.push_back(nod);
nod = t[nod];
}
reverse(a.begin(),a.end());
nod = l2;
b.push_back(nod);
while(nod!=root)
{
nod = t[nod];
b.push_back(nod);
}
reverse(b.begin(),b.end());
for(auto it : a)
{
r.push_back(it);
}
for(auto it : b)
{
r.push_back(it);
}
return r;
}
std::vector<int> longest_trip(int N, int D)
{
n = N;
for(int i=0; i<n; i++)
{
G[i].clear();
sel[i] = false;
t[i] = -1;
}
split = -1, l1 = -1, l2 = -1;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(are_connected({i}, {j}))
{
G[i].push_back(j);
G[j].push_back(i);
}
}
}
vector<int> r;
vector<int> aux = solve_component(0);
if(aux.size() > r.size())
{
r = aux;
}
return r;
}
