#include <bits/stdc++.h>
using namespace std;
#include "longesttrip.h"
namespace {
vector<int> D3(int N){
vector<int> res(N);
iota(res.begin(), res.end(), 0);
return res;
}
vector<int> D2(int N){
bool edge1 = are_connected({0}, {1});
bool edge2 = are_connected({1}, {2});
bool edge3 = are_connected({2}, {0});
deque<int> res;
if (edge1 && edge2){
res.push_back(0); res.push_back(1); res.push_back(2);
}
else if (edge2 && edge3){
res.push_back(1); res.push_back(2); res.push_back(0);
}
else{
res.push_back(2); res.push_back(0); res.push_back(1);
}
for (int i = 3; i < N; i++){
bool e1 = are_connected({i}, {res.front()});
if (e1) res.push_front(i);
else res.push_back(i);
}
vector<int> vres(res.begin(), res.end());
return vres;
}
vector<int> half(int N){
deque<int> path1, path2;
path1.push_back(0); path2.push_back(1);
for (int i = 2; i < N; i++){
if (are_connected({i}, {path1.back()})) path1.push_back(i);
else if (are_connected({i}, {path2.front()})) path2.push_front(i);
else{
path1.insert(path1.end(), path2.begin(), path2.end());
path2.clear(); path2.push_back(i);
}
}
vector<int> v1(path1.begin(), path1.end());
vector<int> v2(path2.begin(), path2.end());
if (v1.size() < v2.size()) return v2;
return v1;
}
}
vector<int> longest_trip(int N, int D){
if (D == 3){
return D3(N);
}
if (D == 2){
return D2(N);
}
return half(N);
}
