#include<bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
vector<int> longest_trip(int N, int D)
{
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> path[2];
path[0] = {0};
for (int i = 1; i < N; i++) {
bool which = uniform_int_distribution<int>(0, 1)(rng);
if (path[which].empty()) {
which = !which;
}
if (are_connected({path[which].back()}, {i})) {
path[which].push_back(i);
if (!path[!which].empty() &&
are_connected({path[!which].back()}, {i})) {
while (!path[!which].empty()) {
path[which].push_back(path[!which].back());
path[!which].pop_back();
}
}
}
else {
path[!which].push_back(i);
}
}
if (path[0].empty()) {
return path[1];
}
if (path[1].empty()) {
return path[0];
}
// if (are_connected({path[0][0], path[0].back()}, {path[1][0], path[1].back()})) {
// vector<int> res;
// if (are_connected({path[0][0]}, {path[1][0]})) {
// for (int i: path[1]) {
// res.push_back(i);
// }
// reverse(res.begin(), res.end());
// for (int i: path[0]) {
// res.push_back(i);
// }
// }
// else if(are_connected({path[0][0]}, {path[1].back()})) {
// for (int i: path[1]) {
// res.push_back(i);
// }
// for (int i: path[0]) {
// res.push_back(i);
// }
// }
// else if(are_connected({path[0].back()}, {path[1][0]})) {
// for (int i: path[0]) {
// res.push_back(i);
// }
// for (int i: path[1]) {
// res.push_back(i);
// }
// }
// else {
// std::cerr << "connection between backs of paths -- impossible\n";
// assert(false);
// }
// return res;
// }
// pair<int, int> connection = find_connection(path[0], path[1]);
vector<int> res = (path[0].size() > path[1].size())?path[0] : path[1];
return res;
}
