// In the name of Allah
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define endl '\n'
#define sep ' '
#define pb push_back
#define Mp make_pair
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
const int maxn = 600 + 7;
int n, d;
bool mark[maxn];
vector<int> res, resx;
vector<int> ls[maxn], vc;
void merge(int i, int j) {
for (int x : ls[j]) ls[i].pb(x);
ls[j].clear(); ls[j].shrink_to_fit();
}
pii get_res(int l, int r) {
if (r - l <= 1) return Mp(l, l);
int mid = (l + r) / 2;
pii f1 = get_res(l, mid), f2 = get_res(mid, r);
vc.clear();
vc.pb(f1.F); vc.pb(f1.S); vc.pb(f2.F); vc.pb(f2.S);
sort(all(vc)); vc.resize(unique(all(vc)) - vc.begin());
while (len(vc) > 2) {
int j1 = vc.back(); vc.pop_back();
int j2 = vc.back(); vc.pop_back();
int j3 = vc.back(); vc.pop_back();
if (are_connected({ls[j1].back()}, {ls[j3][0]})) {
merge(j1, j3);
vc.pb(j1); vc.pb(j2);
}
else if (are_connected({ls[j2].back()}, {ls[j3][0]})) {
merge(j2, j3);
vc.pb(j1); vc.pb(j2);
}
else {
reverse(all(ls[j2]));
merge(j1, j2);
vc.pb(j1); vc.pb(j3);
}
}
return Mp(vc[0], vc[1]);
}
vector<int> longest_trip(int N, int D) {
n = N; d = D;
fill(mark, mark + n, 0);
res.clear(); resx.clear();
for (int i = 0; i < n; i++) {
ls[i].clear(); ls[i].pb(i);
}
if (d >= 2) {
if (are_connected({0}, {1})) {
res.pb(0); mark[0] = 1;
res.pb(1); mark[1] = 1;
}
else {
res.pb(0); mark[0] = 1;
res.pb(2); mark[2] = 1;
}
for (int i = 0; i < n; i++) {
if (mark[i]) continue;
if (are_connected({i}, {res.back()})) res.pb(i);
else {
resx.clear(); swap(res, resx);
res.pb(i);
for (int x : resx) res.pb(x);
}
mark[i] = 1;
}
}
else {
pii f = get_res(0, n);
if (len(ls[f.F]) > len(ls[f.S])) res = ls[f.F];
else res = ls[f.S];
}
return res;
}
