#include "longesttrip.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
std::vector<int> longest_trip(int N, int D)
{
vi trip1,trip2;
trip1.push_back(0);
vi uc;
uc.push_back(0);
for (int i=1;i<N;i++) {
if (uc.size() == 1) {
if (are_connected(trip1,{i})) trip1.push_back(i);
else {
uc.push_back(i);
trip2.push_back(i);
continue;
}
}
else {
int f1 = are_connected(trip1,{i});
int f2 = are_connected(trip2,{i});
if (!f1 && !f2) assert(0);
if (f1 && f2) {
reverse(all(trip2));
trip1.push_back(i);
for (auto it : trip2) trip1.push_back(it);
trip2.clear();
uc.pop_back();
continue;
}
if (f1) {
trip1.push_back(i);
} else trip2.push_back(i);
}
}
if (trip1.size() > trip2.size()) return trip1;
return trip2;
}
