#include "bits/stdc++.h"
#include "longesttrip.h"
#define pb push_back
using namespace std;
vector<int> longest_trip(int N, int D){
if(D == 3){
vector<int> v;
for(int i = 0; i < N; i++){
v.pb(i);
}
return v;
}
if(D == 2){
vector<vector<int> > paths;
for(int i = 0; i + 2 < N; i += 3){
bool c1 = are_connected({i}, {i+1});
bool c2 = are_connected({i+1}, {i+2});
bool c3 = are_connected({i}, {i+2});
if(c1 && c2) paths.pb({i, i+1, i+2});
else if(c1 && c3) paths.pb({i+1, i, i+2});
else if(c2 && c3) paths.pb({i, i+2, i+1});
}
if(N%3 >= 1){
vector<int> lst = paths[paths.size()-1];
int a = lst[0], c = lst.back();
int b = N-1;
bool c1 = are_connected({a}, {b});
bool c2 = are_connected({a}, {c});
bool c3 = are_connected({b}, {c});
if(c1 && c2){
reverse(lst.begin(), lst.end());
// c .... a
lst.pb(b);
paths.pop_back();
paths.pb(lst);
}
else if(c1 && c3){
lst.pb(b);
paths.pop_back();
paths.pb(lst);
}
else if(c2 && c3){
lst.pb(b);
paths.pop_back();
paths.pb(lst);
}
}
if(N%3 >= 2){
vector<int> lst = paths[paths.size()-1];
int a = lst[0], c = lst.back();
int b = N-2;
bool c1 = are_connected({a}, {b});
bool c2 = are_connected({a}, {c});
bool c3 = are_connected({b}, {c});
if(c1 && c2){
reverse(lst.begin(), lst.end());
// c .... a
lst.pb(b);
paths.pop_back();
paths.pb(lst);
}
else if(c1 && c3){
lst.pb(b);
paths.pop_back();
paths.pb(lst);
}
else if(c2 && c3){
lst.pb(b);
paths.pop_back();
paths.pb(lst);
}
}
while(paths.size() > 1){
vector<vector<int> > npaths;
for(int i = 0; i + 1 < paths.size(); i += 2){
int a = paths[i][0], b = paths[i].back(), c = paths[i+1][0];
bool c1 = are_connected({a}, {b});
bool c2 = are_connected({a}, {c});
bool c3 = are_connected({b}, {c});
if(c1 && c2){
vector<int> v = paths[i];
reverse(v.begin(), v.end());
for(auto itr: paths[i+1]) v.pb(itr);
npaths.pb(v);
}
else if(c1 && c3){
vector<int> v = paths[i];
for(auto itr: paths[i+1]) v.pb(itr);
npaths.pb(v);
}
else if(c2 && c3){
vector<int> v = paths[i];
for(auto itr: paths[i+1]) v.pb(itr);
npaths.pb(v);
}
}
if(paths.size()&1){
npaths.pb(paths.back());
}
paths = npaths;
}
return paths[0];
}
if(D == 1){
vector<vector<int> > paths;
for(int i = 0; i < N; i++){
paths.pb({i});
}
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 = are_connected({a}, {c});
bool c3 = are_connected({b}, {c});
if(c1 && c2){
vector<int> v = paths[i];
reverse(v.begin(), v.end());
for(auto itr: paths[i+1]) v.pb(itr);
npaths.pb(v);
}
else if(c1 && c3){
vector<int> v = paths[i];
reverse(v.begin(), v.end());
for(auto itr: paths[i+2]) v.pb(itr);
npaths.pb(v);
}
else if(c2 && c3){
vector<int> v = paths[i+1];
reverse(v.begin(), v.end());
for(auto itr: paths[i+2]) v.pb(itr);
npaths.pb(v);
}
}
if(paths.size() % 3 >= 1){
npaths.pb(paths.back());
}
if(paths.size() % 3 >= 2){
npaths.pb(paths[paths.size()-2]);
}
paths = npaths;
}
if(paths.size() == 1) return paths[0];
if(paths[0].size() > paths[1].size()) return paths[0];
else return paths[1];
}
return {};
}
