#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
// Subtask 1: D == 3
vector<int> sub1(int n) {
vector<int> res(n);
std::iota(res.begin(), res.end(), 0);
return res;
}
// Subtask 2: D == 2
vector<int> sub2(int n) {
vector<int> res {0};
for (int i = 1; i < n; i++) {
if (are_connected({0}, {i})) {
res.push_back(i);
break;
}
}
for (int i = 1; i < n; i++) {
if (i == res[1]) continue;
if (are_connected({res.back()}, {i})) {
res.push_back(i);
} else {
res.insert(res.begin(), i);
}
}
return res;
}
// Subtask 3: D == 1, return path with length >= Lmax / 2
vector<int> sub3(int n) {
// maintain 2 paths
vector<int> p1 {0}, p2 {1};
for (int i = 2; i < n; ++i) {
// consider p1.back(), p2.back(), i
// -> there's at least 1 edge
if (are_connected({p1.back()}, {i})) {
p1.push_back(i);
} else if (are_connected({p2.back()}, {i})) {
p2.push_back(i);
} else {
reverse(p2.begin(), p2.end());
p1.insert(p1.end(), p2.begin(), p2.end());
p2 = {i};
}
}
if (p1.size() > p2.size()) return p1;
return p2;
}
vector<int> longest_trip(int n, int d) {
if (d == 3) return sub1(n);
if (d == 2) return sub2(n);
return sub3(n);
}
