#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int n, d;
vector<vector<int>> paths;
vector<int> longest_trip(int _n, int _d){
n = _n, d = _d;
paths.clear();
for(int i = 0; i < n; ++i)
paths.push_back({i});
mt19937 mt(34234);
while(paths.size() > 2){
int sz = paths.size();
shuffle(paths.begin(), paths.end(), mt);
if(sz == 3){
vector<int> t{sz - 1, sz - 2, sz - 3};
bool ok = false;
for(int i = 0; i < 3 && !ok; ++i){
for(int j = i + 1; j < 3 && !ok; ++j){
if(i == 1 && j == 2){
swap(paths[t[i]], paths.back());
swap(paths[t[j]], paths[sz - 2]);
ok = true;
break;
}
if(are_connected({paths[t[i]][0]}, {paths[t[j]][0]})){
swap(paths[t[i]], paths.back());
swap(paths[t[j]], paths[sz - 2]);
ok = true;
break;
}
}
}
}
else{
if(!are_connected({paths[sz - 1][0]}, {paths[sz - 2][0]})){
if(are_connected({paths[sz - 3][0]}, {paths[sz - 4][0]})){
swap(paths[sz - 1], paths[sz - 3]);
swap(paths[sz - 2], paths[sz - 4]);
}
else{
if(are_connected({paths[sz - 2][0]}, {paths[sz - 3][0]})){
swap(paths[sz - 3], paths[sz - 1]);
}
else{
swap(paths[sz - 3], paths[sz - 2]);
auto u = paths.back();
paths.pop_back();
auto v = paths.back();
paths.pop_back();
reverse(u.begin(), u.end());
for(int x: v)
u.push_back(x);
auto u2 = paths.back();
paths.pop_back();
auto v2 = paths.back();
paths.pop_back();
reverse(u2.begin(), u2.end());
for(int x: v2)
u2.push_back(x);
paths.push_back(u);
paths.push_back(u2);
}
}
}
}
auto u = paths.back();
paths.pop_back();
auto v = paths.back();
paths.pop_back();
reverse(u.begin(), u.end());
for(int x: v)
u.push_back(x);
paths.push_back(u);
}
if(paths.size() == 1)
return paths[0];
if(paths[1].size() > paths[0].size())
swap(paths[0], paths[1]);
bool conn = false;
if(are_connected({paths[0][0]}, {paths[1][0]})){
conn = true;
}
else if(are_connected({paths[0][0]}, {paths[1].back()})){
reverse(paths[1].begin(), paths[1].end());
conn = true;
}
else if(are_connected({paths[0].back()}, {paths[1][0]})){
reverse(paths[0].begin(), paths[0].end());
conn = true;
}
else if(are_connected({paths[0].back()}, {paths[1].back()})){
reverse(paths[0].begin(), paths[0].end());
reverse(paths[1].begin(), paths[1].end());
conn = true;
}
if(conn){
reverse(paths[0].begin(), paths[0].end());
for(int x: paths[1])
paths[0].push_back(x);
return paths[0];
}
if(!are_connected(paths[0], paths[1]))
return paths[0];
auto get_prefix = [](const vector<int> &v, int idx){
vector<int> ret;
for(int i = 0; i <= idx; ++i)
ret.push_back(v[i]);
return ret;
};
int l1 = 0, r1 = (int)paths[0].size() - 1;
while(l1 != r1){
int mid = (l1 + r1) >> 1;
if(are_connected(get_prefix(paths[0], mid), paths[1]))
r1 = mid;
else
l1 = mid + 1;
}
int l2 = 0, r2 = (int)paths[1].size() - 1;
while(l2 != r2){
int mid = (l2 + r2) >> 1;
if(are_connected({paths[0][l1]}, get_prefix(paths[1], mid)))
r2 = mid;
else
l2 = mid + 1;
}
vector<int> ans;
for(int i = l1 + 1; i < (int)paths[0].size(); ++i)
ans.push_back(paths[0][i]);
for(int i = 0; i <= l1; ++i)
ans.push_back(paths[0][i]);
for(int i = l2; i < (int)paths[1].size(); ++i)
ans.push_back(paths[1][i]);
for(int i = 0; i < l2; ++i)
ans.push_back(paths[1][i]);
return ans;
}
