#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define pf push_front
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
bool edge(int i, int j){
return are_connected({i},{j});
}
vector<int> longest_trip(int N, int D)
{
vector<int> v; deque<int> dq;
v.clear(); dq.clear();
dq.pb(0); int i = 1;
while(sz(dq)<N){
if(i==1){
if(edge(0,1)){
dq.pb(1);
if(edge(1,2)) dq.pb(2);
else dq.pf(2);
}
else{
dq.pb(2); dq.pb(1);
}
i = 3;
}
else{
if(edge(dq.back(),i)) dq.pb(i);
else dq.pf(i);
i++;
}
}
for(auto u : dq) v.pb(u);
return v;
}
