#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
vector<int> longest_trip(int N, int D)
{
/*vector<vi> edges(N);
for(int i = 0; i < N; i++)
{
for(int j = i+1; j <N; j++)
{
if(are_connected({i}, {j}))
{
edges[i].push_back(j);
edges[j].push_back(i);
}
}
}
vi distance(N, -1);
vi previous(N, -1);
auto dfs = [&](auto &&self, int at, int d, int from) -> void {
if(distance[at] != -1)
return;
distance[at] = d;
previous[at] = from;
for(auto to: edges[at])
if(distance[to] == -1)
self(self, to, d+1, at);
};
int mx = 0;
vi path;
for(int i = 0; i < N; i++)
{
distance.assign(N, -1);
dfs(dfs, i, 0, -1);
auto it = max_element(distance.begin(), distance.end());
if(*it > mx)
{
mx = *it;
auto at = it - distance.begin();
while(at != -1) {
path.push_back(at);
at = previous[at];
}
}
}
return path; */
vector<int> a, b;
a.push_back(0);
for(int i = 1; i < N; i++)
{
bool ac = are_connected({i}, {a.back()});
if(b.empty())
{
if(ac)
a.push_back(i);
else
b.push_back(i);
continue;
}
bool bc = are_connected({i}, {b.back()});
if(ac && bc)
{
a.push_back(i);
for(int j = b.size() - 1; j >= 0; j--)
a.push_back(b[j]);
b.clear();
}
else if(ac)
{
a.push_back(i);
} else if(bc)
{
b.push_back(i);
} else {
for(int j = b.size() - 1; j >= 0; j--)
a.push_back(b[j]);
b.clear();
b.push_back(i);
}
}
if(b.empty())
return a;
if(a.empty())
return b;
bool afbf = are_connected({a.front()}, {b.front()});
if(afbf)
{
a.insert(a.begin(), b.rbegin(), b.rend());
return a;
}
bool afbb = are_connected({a.front()}, {b.back()});
if(afbb)
{
a.insert(a.begin(), b.begin(), b.end());
return a;
}
// b is cycle
bool abbf = are_connected({a.back()}, {b.front()});
if(afbf)
{
a.insert(a.end(), b.begin(), b.end());
return a;
}
bool abbb = are_connected({a.back()}, {b.back()});
if(afbb)
{
a.insert(a.end(), b.rbegin(), b.rend());
return a;
}
// a is ook cycle
bool ab = are_connected(a, b);
if(!ab)
{
if(a.size() > b.size())
return a;
return b;
}
int anode;
for(int i = 0; i < a.size(); i++)
{
if(are_connected({a[i]}, b))
anode = i;
}
int bnode;
for(int i = 0; i < b.size(); i++)
{
if(are_connected({b[i]}, {anode}))
bnode = i;
}
vector<int> out;
for(int i = anode + 1; i < a.size(); i++)
out.push_back(a[i]);
for(int i = 0; i <= anode; i++)
out.push_back(a[i]);
for(int i = bnode; i < b.size(); i++)
out.push_back(b[i]);
for(int i = 0; i < bnode; i++)
out.push_back(b[i]);
return out;
}
