#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
std::vector<int> longest_trip(int N, int D)
{
int n = N;
vector<int> v1;
vector<int> v2;
v1.push_back(0);
v2.push_back(1);
for (int x = 2; x < n; ++x)
{
if (are_connected(vector<int>{x}, vector<int>{v1.back()}))
v1.push_back(x);
else if (are_connected(vector<int>{x}, vector<int>{v2.back()}))
v2.push_back(x);
else
{
reverse(all(v2));
for (int i = 0; i < sz(v2); ++i)
v1.push_back(v2[i]);
v2.clear();
v2.push_back(x);
}
}
if (sz(v1) > sz(v2))
return v1;
return v2;
}
