#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
const int nmax = 256;
int n;
int d[nmax + 5];
bool sel[nmax + 5];
int t[nmax + 5];
int split, l1, l2;
int find_next_go(int nod)
{
vector<int> l;
for(int i=0; i<n; i++)
{
if(!sel[i])
{
l.push_back(i);
}
}
if(l.empty() || !are_connected({nod},l))
{
return -1;
}
int st = 0;
int dr = l.size();
while(st<dr)
{
int mij = (st + dr) >> 1;
vector<int> aux;
for(int i=st; i<=mij; i++)
{
aux.push_back(l[i]);
}
if(are_connected({nod},aux))
{
dr = mij;
}
else
{
st = mij + 1;
}
}
return l[st];
}
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)
{
split = -1, l1 = -1, l2 = -1;
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 = are_connected({l1}, {root});
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++)
{
sel[i] = false;
t[i] = -1;
}
vector<int> r;
for(int i=0; i<n; i++)
{
if(sel[i])
{
continue;
}
vector<int> aux = solve_component(i);
if(aux.size() > r.size())
{
r = aux;
}
}
return r;
}
