// 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);
int j1 = f.F, j2 = f.S;
if (!are_connected(ls[j1], ls[j2])) {
if (len(ls[j1]) >= len(ls[j2])) res = ls[j1];
else res = ls[j2];
}
else {
if (are_connected({ls[j1].back()}, {ls[j2][0]})) {
merge(j1, j2);
res = ls[j1];
}
else if (are_connected({ls[j1].back()}, {ls[j2].back()})) {
reverse(all(ls[j2]));
merge(j1, j2);
res = ls[j1];
}
else if (are_connected({ls[j1][0]}, {ls[j2][0]})) {
reverse(all(ls[j1]));
merge(j1, j2);
res = ls[j1];
}
else if (are_connected({ls[j1][0]}, {ls[j2].back()})) {
reverse(all(ls[j1])); reverse(all(ls[j2]));
merge(j1, j2);
res = ls[j1];
}
else {
int lx = 0, rx = len(ls[j1]);
while (rx - lx > 1) {
int mid = (lx + rx) / 2;
vc.clear();
for (int i = lx; i < mid; i++) vc.pb(ls[j1][i]);
if (are_connected(vc, ls[j2])) rx = mid;
else lx = mid;
}
int i1 = lx, v1 = ls[j1][i1];
lx = 0, rx = len(ls[j2]);
while (rx - lx > 1) {
int mid = (lx + rx) / 2;
vc.clear();
for (int i = lx; i < mid; i++) vc.pb(ls[j2][i]);
if (are_connected({v1}, vc)) rx = mid;
else lx = mid;
}
int i2 = lx, v2 = ls[j2][i2];
for (int i = (i1 + 1); i < (i1 + 1 + len(ls[j1])); i++) {
res.pb(ls[j1][i % len(ls[j1])]);
}
for (int i = i2; i < (i2 + len(ls[j2])); i++) {
res.pb(ls[j2][i % len(ls[j2])]);
}
}
}
}
return res;
}
