#include<bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
bool c_edge(int u, int v)
{
return are_connected({u}, {v});
}
vector<int> longest_trip(int n, int d)
{
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v1;
vector<int> v2;
bool enemy = false;
vector<int> SSS(n);
for(int i = 0; i < n; i++)
SSS[i] = i;
shuffle(SSS.begin(), SSS.end(), rng);
for(int Sr = 0; Sr < n; Sr++)
{
int i = SSS[Sr];
if(v1.size() < v2.size())
swap(v1, v2);
if(v1.empty())
{
v1.pb(i);
continue;
}
if(v2.empty())
{
v2.pb(i);
continue;
}
if(c_edge(v1.back(), i))
{
v1.pb(i);
enemy = false;
continue;
}
else if(enemy)
{
v2.pb(i);
continue;
}
if(c_edge(v2.back(), i))
{
v2.pb(i);
enemy = true;
continue;
}
while(v1.size())
{
v2.pb(v1.back());
v1.pob();
}
v1.pb(i);
enemy = false;
}
if(c_edge(v1.back(), v2.back()))
{
while(v1.size())
{
v2.pb(v1.back());
v1.pob();
}
return v2;
}
if(c_edge(v1.front(), v2.back()))
{
reverse(v1.begin(), v1.end());
while(v1.size())
{
v2.pb(v1.back());
v1.pob();
}
return v2;
}
reverse(v2.begin(), v2.end());
if(c_edge(v1.back(), v2.back()))
{
while(v1.size())
{
v2.pb(v1.back());
v1.pob();
}
return v2;
}
if(c_edge(v1.front(), v2.back()))
{
reverse(v1.begin(), v1.end());
while(v1.size())
{
v2.pb(v1.back());
v1.pob();
}
return v2;
}
if(v1.empty())
return v2;
if(v2.empty())
return v1;
if(v1.size() > v2.size())
swap(v1, v2);
if(!are_connected(v1, v2))
return v2;
int l = 0;
int r = v2.size()-1;
while(l < r)
{
int m = (l+r)/2;
vector<int> s = v2;
s.resize(m+1);
if(are_connected(v1, s))
r = m;
else
l = m+1;
}
int S2 = l;//v2[S] is target.
l = 0;
r = v1.size()-1;
while(l < r)
{
int m = (l+r)/2;
vector<int> s = v1;
s.resize(m+1);
if(are_connected({v2[S2]}, s))
r = m;
else
l = m+1;
}
int S1 = l; //v1[S1], v2[S2] are connected.
//(n-1-S1)
vector<int> pth;
for(int i = S1-1; i >= 0; i--)
pth.pb(v1[i]);
for(int i = v1.size()-1; i >= S1; i--)
pth.pb(v1[i]);
for(int i = S2; i < v2.size(); i++)
pth.pb(v2[i]);
for(int i = 0; i < S2; i++)
pth.pb(v2[i]);
return pth;
}
