#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<vector<int>, vector<int>> pvv;
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
ll res = 1;
while(b > 0) {
if(b%2 == 1) res = MOD(res * a, mod);
b /= 2;
a = MOD(a * a, mod);
}
return res;
}
int t, n;
pvv merge3(vector<int> v1, vector<int> v2, vector<int> v3) {
if(are_connected({v1[0]}, {v2[0]}) == 1) {
reverse(all(v1));
for(auto it : v2) v1.pb(it);
return {v1, v3};
}
if(are_connected({v1[0]}, {v3[0]}) == 1) {
reverse(all(v1));
for(auto it : v3) v1.pb(it);
return {v1, v2};
}
reverse(all(v2));
for(auto it : v3) v2.pb(it);
return {v1, v2};
}
pvv merge2(vector<int> v1, vector<int> v2) {
if(size(v1) > 1 && are_connected({v1[0]}, {v1.back()}) == 0) {
if(are_connected({v1[0]}, {v2[0]}) == 1) {
reverse(all(v1));
}
for(auto it : v2) v1.pb(it);
return {v1, {}};
}
if(size(v2) > 1 && are_connected({v2[0]}, {v2.back()}) == 0) {
if(are_connected({v2[0]}, {v1[0]}) == 1) {
reverse(all(v2));
}
for(auto it : v1) v2.pb(it);
return {v2, {}};
}
if(size(v1) > size(v2)) swap(v1, v2);
vector<int> tmp = v1, tmp2 = v2;
if(are_connected(tmp, tmp2) == 0) {
return {v1, v2};
}
while(size(tmp) > 1) {
vector<int> tt;
for(int i=size(tmp)/2; i<size(tmp); i++) {
tt.pb(tmp[i]);
}
if(are_connected(tt, tmp2) == 1) {
tmp = tt;
} else {
int x = size(tmp) / 2;
while(size(tmp) > x) tmp.pop_back();
}
}
while(size(tmp2) > 1) {
vector<int> tt;
for(int i=size(tmp2)/2; i<size(tmp2); i++) {
tt.pb(tmp2[i]);
}
if(are_connected(tt, tmp) == 1) {
tmp2 = tt;
} else {
int x = size(tmp2) / 2;
while(size(tmp2) > x) tmp2.pop_back();
}
}
int id = 0, id2 = 0;
for(int i=0; i<size(v1); i++) {
if(v1[i] == tmp[0]) id = i;
}
for(int i=0; i<size(v2); i++) {
if(v2[i] == tmp2[0]) id2 = i;
}
vector<int> res;
for(int i=id+1; i<size(v1); i++) res.pb(v1[i]);
for(int i=0; i<=id; i++) res.pb(v1[i]);
for(int i=id2; i<size(v2); i++) res.pb(v2[i]);
for(int i=0; i<id2; i++) res.pb(v2[i]);
return {res, {}};
}
pvv divide(int l, int r) {
if(l == r) {
return {{l}, {}};
}
if(l == r - 1) {
if(are_connected({l}, {r}) == 1) {
return {{l, r}, {}};
}
return {{l}, {r}};
}
int mid = (l + r) / 2;
pvv r1 = divide(l, mid), r2 = divide(mid+1, r);
vector<vector<int>> paths;
paths.pb(r1.F);
paths.pb(r2.F);
if(size(r1.S) > 0) paths.pb(r1.S);
if(size(r2.S) > 0) paths.pb(r2.S);
while(size(paths) >= 3) {
int x = size(paths) - 1;
pvv tmp = merge3(paths[x], paths[x-1], paths[x-2]);
paths.pop_back();paths.pop_back();paths.pop_back();
paths.pb(tmp.F);
paths.pb(tmp.S);
}
pvv tmp = merge2(paths[0], paths[1]);
return tmp;
}
vector<int> longest_trip(int _N, int _D) {
n = _N;
pvv ans = divide(0, n-1);
if(size(ans.F) > size(ans.S)) {
// for(auto it : ans.F) {fuck(it);}
// for(auto it : ans.S) {fuck(it);}
return ans.F;
}
// for(auto it : ans.F) {fuck(it);}
// for(auto it : ans.S) {fuck(it);}
return ans.S;
}
