#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 l = 0, r= a.size();
while(l+1 != r)
{
int m = (l+r+1)/2;
vi c;
for(int i = l; i < m; i++)
c.push_back(a[i]);
if(are_connected(c, b))
{
r = m;
} else
l = m;
}
int anode = l;
l = 0, r= b.size();
while(l+1 != r)
{
int m = (l+r+1)/2;
vi c;
for(int i = l; i < m; i++)
c.push_back(b[i]);
if(are_connected(c, {a[anode]}))
{
r = m;
} else
l = m;
}
int bnode = l;
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;
}
