#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<random>
#include "longesttrip.h"
using namespace std;
mt19937 rng(87645);
vector<int>ans;
int n;
int cntqueries=0;
bool edge(int u,int v)
{
cntqueries++;
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);
vector<int>nodes;
for(int i=2;i<n;i++)nodes.push_back(i);
shuffle(nodes.begin(),nodes.end(),rng);
for(int i:nodes)
{
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(cntqueries>500)while(1);
if(v1.size()>v2.size())ans=v1;
else ans=v2;
return ans;
}
