#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int dosta = 1e5;
vector<int> longest_trip(int n, int d){
srand(time(0));
vector <int> v;
for(int i = 0; i < n; i++) v.push_back(i);
for(int i = 0; i < dosta; i++){
int p1 = rand() % n;
int p2 = rand() % n;
if(p1 != p2) swap(v[p1], v[p2]);
}
vector <int> a, b;
a.push_back(0);
for(int i = 1; i < n; i++){
//if(rand() % 2) swap(a, b);
if(are_connected({a.back()}, {v[i]})) a.push_back(v[i]);
else if(b.empty() || are_connected({b.back()}, {v[i]})) b.push_back(v[i]);
else {
while(!b.empty()){
a.push_back(b.back());
b.pop_back();
}
b.push_back(v[i]);
}
}
if(a.size() < b.size()) swap(a, b);
return a;
}
