#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#define G are_connected
int n;
vector<vector<signed> > v;
vector<signed> rev(vector<signed> v){
reverse(all(v));
return v;
}
vector<signed> concat(vector<signed> a,vector<signed> b){
a.insert(a.end(),all(b));
return a;
}
vector<signed> longest_trip(signed N, signed D){
n=N;
v.clear();
rep(x,0,n) v.pub({x});
while (sz(v)>=3){
swap(v.back(),v[rng()%sz(v)]); vector<signed> a=v.back(); v.pob();
swap(v.back(),v[rng()%sz(v)]); vector<signed> b=v.back(); v.pob();
swap(v.back(),v[rng()%sz(v)]); vector<signed> c=v.back(); v.pob();
if (rng()%2==0) swap(b,a);
if (rng()%3==0) swap(c,a);
else if (rng()%2==0) swap(c,b);
if (G({a.back()},{b.back()})){
swap(a,c);
v.pub(a);
v.pub(concat(b,rev(c)));
continue;
}
if (G({a.back()},{c.back()})){
swap(a,b);
}
vector<signed> d;
if (!v.empty()){
swap(v.back(),v[rng()%sz(v)]); d=v.back();
}
if (!d.empty() && G({a.back()},{d.back()})){
v.pob();
v.pub(concat(a,rev(d)));
v.pub(concat(b,rev(c)));
}
else{
v.pub(a);
v.pub(concat(b,rev(c)));
}
}
//cout<<"2 cyc"<<endl;
//for (auto it:v[0]) cout<<it<<" "; cout<<endl;
//for (auto it:v[1]) cout<<it<<" "; cout<<endl;
if ((sz(v[0])==1 || G({v[0].front()},{v[0].back()})) && (sz(v[1])==1 || G({v[1].front()},{v[1].back()}))){
vector<signed> l=v[0],r=v[1];
if (!G(v[0],v[1])) return (sz(v[0])>sz(v[1])?v[0]:v[1]);
while (sz(l)>1){
vector<signed> a,b;
rep(x,0,sz(l)/2) a.pub(l[x]);
rep(x,sz(l)/2,sz(l)) b.pub(l[x]);
if (G(a,r)) l=a;
else l=b;
}
while (sz(r)>1){
vector<signed> a,b;
rep(x,0,sz(r)/2) a.pub(r[x]);
rep(x,sz(r)/2,sz(r)) b.pub(r[x]);
if (G(l,a)) r=a;
else r=b;
}
int idxl,idxr;
rep(x,0,sz(v[0])) if (v[0][x]==l[0]) idxl=x;
rep(x,0,sz(v[1])) if (v[1][x]==r[0]) idxr=x;
vector<signed> res;
rep(x,0,sz(v[0])) res.pub(v[0][(idxl+1+x)%sz(v[0])]);
rep(x,0,sz(v[1])) res.pub(v[1][(idxr+x)%sz(v[1])]);
return res;
}
else{
if (G({v[0].front()},{v[1].front()})) return concat(rev(v[0]),v[1]);
if (G({v[0].front()},{v[1].back()})) return concat(rev(v[0]),rev(v[1]));
if (G({v[0].back()},{v[1].front()})) return concat(v[0],v[1]);
if (G({v[0].back()},{v[1].back()})) return concat(v[0],rev(v[1]));
return (sz(v[0])>sz(v[1])?v[0]:v[1]);
}
}
