#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include "longesttrip.h"
using namespace std;
vector<int>ans;
int n;
bool edge(int u,int v)
{
return are_connected({u},{v});
}
std::vector<int> longest_trip(int N, int D)
{
n=N;
ans.clear();
///reset eveerything
vector<int>v1,v2;
v1.push_back(0);v2.push_back(1);
for(int i=2;i<n;i++)
{
if(edge(i,v1.back()))v1.push_back(i);
else if(edge(i,v2.back()))v2.push_back(i);
else
{
vector<int>tmp=v1;
reverse(v2.begin(),v2.end());
for(int x:v2)tmp.push_back(x);
v1=tmp;
v2.clear();v2.push_back(i);
}
}
if(v1.size()>v2.size())ans=v1;
else ans=v2;
return ans;
}
