#include "longesttrip.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
std::vector<int> longest_trip(int n, int d)
{
vector<int> ans;
vector<int> comp, comp1;
ll p[n];
iota(p, p + n, 0);
shuffle(p, p + n, rng);
bool idk = true;
for (int i : p)
if (comp1.empty())
{
if (comp.empty())
{
comp = {i};
continue;
}
if (!are_connected({comp.back()}, {i}))
comp1 = {i}, idk = false;
else
comp.push_back(i);
}
else if (comp.empty())
{
if (!are_connected({comp1.back()}, {i}))
comp = {i}, idk = false;
else
comp1.push_back(i);
}
else
{
bool ok = are_connected({comp.back()}, {i});
if (ok)
comp.push_back(i), idk = true;
else
{
if (!idk) comp1.push_back(i), idk = false;
else
{
if (are_connected({comp1.back()}, {i})) comp1.push_back(i), idk = false;
else
{
for (ll i = comp1.size() - 1; i >= 0; i--) comp.push_back(comp1[i]);
comp1 = {i};
idk = false;
}
}
}
}
if (comp1.empty())
return comp;
if (comp.size() > comp1.size())
swap(comp, comp1);
if (!are_connected(comp, comp1))
return comp1;
if (comp1.size() >= 3)
{
bool ok;
if (comp.size() >= 3)
{
ok = are_connected({comp.front()}, {comp.back()});
if (!ok)
{
ans = comp;
if (!are_connected({comp.back()}, {comp1.front()}))
reverse(ans.begin(), ans.end());
for (ll i : comp1)
ans.push_back(i);
return ans;
}
}
swap(comp, comp1);
if (comp.size() >= 3)
{
ok = are_connected({comp.front()}, {comp.back()});
if (!ok)
{
ans = comp;
if (!are_connected({comp.back()}, {comp1.front()}))
reverse(ans.begin(), ans.end());
for (ll i : comp1)
ans.push_back(i);
return ans;
}
}
swap(comp, comp1);
}
ll l = 0, r = comp.size() - 1;
int first = comp.size() - 1;
vector<int> tmp;
while (l <= r)
{
tmp.clear();
ll mid = (l + r) >> 1;
for (ll i = 0; i <= mid; i++)
tmp.push_back(comp[i]);
if (are_connected(tmp, comp1))
r = mid - 1, first = mid;
else
l = mid + 1;
}
l = 0, r = comp1.size() - 1;
int second = comp1.size() - 1;
while (l <= r)
{
tmp.clear();
ll mid = (l + r) >> 1;
for (ll i = 0; i <= mid; i++)
tmp.push_back(comp1[i]);
if (are_connected({comp[first]}, tmp))
r = mid - 1, second = mid;
else
l = mid + 1;
}
for (ll i = first + comp.size() - 1; i >= first; i--)
ans.push_back(comp[i % comp.size()]);
for (ll i = second; i < second + comp1.size(); i++)
ans.push_back(comp1[i % comp1.size()]);
return ans;
}
