#include "bits/stdc++.h"
#include "longesttrip.h"
#define pb push_back
using namespace std;
vector<int> longest_trip(int N, int D){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> paths[2], p(N);
for(int i = 0; i < N; i++){
p[i] = i;
}
shuffle(p.begin(), p.end(), rng);
int last = -1;
paths[0].pb(p[0]);
paths[1].pb(p[1]);
for(int i = 2; i < N; i++){
bool c1 = are_connected({p[i]}, {paths[0].back()});
if(c1){
paths[0].pb(p[i]);
last = 0;
continue;
}
if(last == 1){
paths[1].pb(p[i]);
last = -1;
continue;
}
bool c2 = are_connected({p[i]}, {paths[1].back()});
if(c2){
paths[1].pb(p[i]);
last = 1;
continue;
}
while(paths[1].size()){
paths[0].pb(paths[1].back());
paths[1].pop_back();
}
paths[1].pb(p[i]);
last = -1;
}
bool check = are_connected(paths[0], paths[1]);
if(paths[1].size() > paths[0].size()) swap(paths[0], paths[1]);
if(!check){
return paths[0];
}
else{
if(paths[1].size() == 1){ // bu if buglı
int a = paths[0][0], b = paths[0].back(), c = paths[1][0];
bool ftype = are_connected({a, b}, {c});
if(ftype){
bool c3 = 0;
bool c2 = are_connected({b}, {c});
if(c2){
paths[0].pb(c);
return paths[0];
}
else{
c3 = are_connected({c}, {a});
}
if(c3){
reverse(paths[0].begin(), paths[0].end());
paths[0].pb(c);
return paths[0];
}
}
int l = 0, r = paths[0].size()-1;
while(l < r){
int m = (l + r)/2;
vector<int> v;
for(int i = l; i <= m; i++){
v.pb(paths[0][i]);
}
bool check = are_connected(v, {c});
if(check) r = m;
else l = m+1;
}
int x = paths[0][l];
vector<int> updpath;
for(auto itr: paths[0]){
updpath.pb(itr);
if(itr == x) break;
}
updpath.pb(c);
reverse(updpath.begin(), updpath.end());
reverse(paths[0].begin(), paths[0].end());
for(auto itr: paths[0]){
if(itr == x) break;
updpath.pb(itr);
}
return updpath;
}
else{
int a = paths[0][0], b = paths[0].back(), c = paths[1][0], d = paths[1].back();
bool ftype = are_connected({a, b}, {c, d});
if(ftype){
bool c2 = are_connected({b}, {c});
bool c3 = 0;
if(c2){
vector<int> v = paths[0];
for(auto itr: paths[1]) v.pb(itr);
return v;
}
else{
c3 = are_connected({c}, {a});
}
if(c3){
vector<int> v = paths[0];
reverse(v.begin(), v.end());
for(auto itr: paths[1]) v.pb(itr);
return v;
}
bool c5 = are_connected({a}, {d});
bool c6 = 0;
if(c5){
vector<int> v = paths[0];
reverse(v.begin(), v.end());
reverse(paths[1].begin(), paths[1].end());
for(auto itr: paths[1]) v.pb(itr);
return v;
}
else{
c6 = are_connected({b}, {d});
}
if(c6){
vector<int> v = paths[1];
reverse(paths[0].begin(), paths[0].end());
for(auto itr: paths[0]) v.pb(itr);
return v;
}
}
// şimdi ikisinin de cycle olduğunu biliyoruz
pair<int, int> p = {-1, -1};
int l = 0, r = paths[1].size()-1;
while(l < r){
int m = (l + r)/2;
vector<int> v;
for(int i = l; i <= m; i++){
v.pb(paths[1][i]);
}
bool check = are_connected(paths[0], v);
if(check) r = m;
else l = m+1;
}
int sec = paths[1][l];
l = 0, r = paths[0].size()-1;
while(l < r){
int m = (l + r)/2;
vector<int> v;
for(int i = l; i <= m; i++){
v.pb(paths[0][i]);
}
bool check = are_connected({sec}, v);
if(check) r = m;
else l = m+1;
}
int fir = paths[0][l];
p = {fir, sec};
vector<int> ans;
for(auto itr: paths[0]){
if(itr == p.first) break;
ans.pb(itr);
}
reverse(ans.begin(), ans.end());
reverse(paths[0].begin(), paths[0].end());
for(auto itr: paths[0]){
ans.pb(itr);
if(itr == p.first) break;
} // son eleman p.first
vector<int> ans2;
for(auto itr: paths[1]){
if(itr == p.second) break;
ans2.pb(itr);
}
reverse(ans2.begin(), ans2.end());
reverse(paths[1].begin(), paths[1].end());
for(auto itr: paths[1]){
ans2.pb(itr);
if(itr == p.second) break;
} // son eleman p.second
vector<int> v = ans;
reverse(ans2.begin(), ans2.end());
for(auto itr: ans2) v.pb(itr);
return v;
}
}
}
