#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());
if(D == 1){
vector<vector<int> > paths;
for(int i = 0; i < N; i++){
paths.pb({i});
}
shuffle(paths.begin(), paths.end(), rng);
while(paths.size() > 2){
vector<vector<int> > npaths;
for(int i = 0; i + 2 < paths.size(); i += 3){
int a = paths[i][0], b = paths[i+1][0], c = paths[i+2][0];
bool c1 = are_connected({a}, {b});
bool c2 = 0;
if(c1){
vector<int> v = paths[i];
reverse(v.begin(), v.end());
for(auto itr: paths[i+1]) v.pb(itr);
npaths.pb(v);
npaths.pb(paths[i+2]);
continue;
}
else{
c2 = are_connected({a}, {c});
}
if(c2){
vector<int> v = paths[i];
reverse(v.begin(), v.end());
for(auto itr: paths[i+2]) v.pb(itr);
npaths.pb(v);
npaths.pb(paths[i+1]);
}
else{
vector<int> v = paths[i+1];
reverse(v.begin(), v.end());
for(auto itr: paths[i+2]) v.pb(itr);
npaths.pb(v);
npaths.pb(paths[i]);
}
}
if(paths.size() % 3 >= 1){
npaths.pb(paths[paths.size()-1]);
}
if(paths.size() % 3 >= 2){
npaths.pb(paths[paths.size()-2]);
}
paths = npaths;
shuffle(paths.begin(), paths.end(), rng);
}
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 c1 = are_connected({a}, {b});
bool c2 = are_connected({b}, {c});
bool c3 = are_connected({c}, {a});
if(c2){
paths[0].pb(c);
return paths[0];
}
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 = 0; 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 c2 = are_connected({b}, {c});
bool c3 = are_connected({c}, {a});
if(c2){
vector<int> v = paths[0];
for(auto itr: paths[1]) v.pb(itr);
return v;
}
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 = are_connected({b}, {d});
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;
}
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 = 0; 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 = 0; 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;
}
}
}
return {};
}
