#include <bits/stdc++.h>
using namespace std;
#include "longesttrip.h"
namespace {
vector<int> D3(int N, int D){
vector<int> res(N);
iota(res.begin(), res.end(), 0);
return res;
}
vector<int> D2(int N, int D){
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> longest_trip(int N, int D){
if (D == 3){
return D3(N, D);
}
if (D == 2){
return D2(N, D);
}
return {};
}
