// In the name of Allah
#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = (1 << 10) + 4;
int n;
vector<int> ls1, ls2, lsx;
vector<int> A1, A2;
bool askx(int u, int v) {
return are_connected({u}, {v});
}
void addx(int v1, int v2) {
if (askx(v1, v2)) {
if (len(ls1) == 0) {
ls1.pb(v1); ls1.pb(v2);
return ;
}
else if (len(ls2) == 0) {
if (askx(ls1.back(), v1)) {
ls1.pb(v1); ls1.pb(v2);
return ;
}
else {
ls2.pb(v2); ls2.pb(v1);
return ;
}
}
if (askx(ls1.back(), v1)) {
if (!askx(ls2.back(), v2)) {
ls1.pb(v1); ls1.pb(v2);
return ;
}
else {
ls1.pb(v1); ls1.pb(v2); reverse(all(ls2));
for (int x : ls2) ls1.pb(x);
ls2.clear();
}
}
else {
if (!askx(ls1.back(), v2)) {
ls2.pb(v1); ls2.pb(v2);
return ;
}
else {
ls2.pb(v1); ls2.pb(v2); reverse(all(ls1));
for (int x : ls1) ls2.pb(x);
ls1.clear(); ls1.swap(ls2);
}
}
}
else {
if (len(ls1) == 0) {
ls1.pb(v1); ls2.pb(v2);
return ;
}
else if (len(ls2) == 0) {
if (askx(ls1.back(), v1)) {
ls1.pb(v1); ls2.pb(v2);
return ;
}
else {
ls1.pb(v2); ls2.pb(v1);
return ;
}
}
if (!askx(ls1.back(), v1)) {
ls2.pb(v1); ls1.pb(v2);
return ;
}
else {
if (askx(ls2.back(), v2)) {
ls1.pb(v1); ls2.pb(v2);
return ;
}
else {
ls2.pb(v1); ls1.pb(v2);
return ;
}
}
}
}
void addw(int v1) {
if (len(ls2) == 0) {
if (askx(ls1.back(), v1)) ls1.pb(v1);
else ls2.pb(v1);
return ;
}
if (!askx(ls1.back(), v1)) ls2.pb(v1);
else if (!askx(ls2.back(), v1)) ls1.pb(v1);
else {
ls1.pb(v1); reverse(all(ls2));
for (int x : ls2) ls1.pb(x);
ls2.clear();
}
}
bool okx(int l1, int r1, int l2, int r2) {
A1.clear(); A2.clear();
for (int i = l1; i < r1; i++) A1.pb(ls1[i]);
for (int i = l2; i < r2; i++) A2.pb(ls2[i]);
return are_connected(A1, A2);
}
vector<int> longest_trip(int N, int D) {
n = N; ls1.clear(); ls2.clear();
for (int i = 0; i < n; i += 2) {
if (i + 1 < n) addx(i, i + 1);
else addw(i);
}
if (len(ls2) == 0) return ls1;
if (!are_connected(ls1, ls2)) {
if (len(ls1) > len(ls2)) return ls1;
else return ls2;
}
for (int T = 0; T < 2; T++) {
if (ls2[0] != ls2.back() && !askx(ls2[0], ls2.back())) {
if (askx(ls1.back(), ls2[0])) {
for (int x : ls2) ls1.pb(x);
ls2.clear();
return ls1;
}
else {
reverse(all(ls2));
for (int x : ls2) ls1.pb(x);
ls2.clear();
return ls1;
}
}
ls1.swap(ls2);
}
int l1 = 0, r1 = len(ls1);
int l2 = 0, r2 = len(ls2);
while (r1 - l1 > 1) {
int mid = (l1 + r1) / 2;
if (okx(l1, mid, l2, r2)) r1 = mid;
else l1 = mid;
}
while (r2 - l2 > 1) {
int mid = (l2 + r2) / 2;
if (okx(l1, r1, l2, mid)) r2 = mid;
else l2 = mid;
}
lsx.clear();
for (int i = l1; i < l1 + len(ls1); i++) {
lsx.pb(ls1[i % len(ls1)]);
}
reverse(all(lsx));
for (int i = l2; i < l2 + len(ls2); i++) {
lsx.pb(ls2[i % len(ls2)]);
}
return lsx;
}
