#include "longesttrip.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,sse4,bmi2,popcnt")
#define int long long
#define iint signed
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)((x).size()))
#define SQ(x) ((x)*(x))
#define pii pair<int,int>
#define pipii pair<int,pii>
#define ppi pair<pii,int>
#define Graph vector<vector<int>>
#define Graphw vector<vector<pii>>
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define md(x) (((x)%(mod)+(mod))%(mod))
#define MD(x,M) (((x)%(M)+(M))%(M))
#define ld long double
#define pdd pair<ld,ld>
template<typename S> void chmin(S &x,S y) { x=min(x,y); }
template<typename S> void chmax(S &x,S y) { x=max(x,y); }
#define addmod(x,y) x=((x+(y))%mod)
#define Vi vector<int>
#define Vpii vector<pii>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) {cout<<(#x)<<":";for(auto allen:(x)) cout<<allen<<" ";cout<<" size="<<(x).size()<<endl;}
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& os,pair<T1,T2> p) { return os<<'{'<<p.f<<','<<p.s<<'}'; }
template<typename T1,typename T2>
istream& operator>>(istream& os,pair<T1,T2> &p) { return os>>p.f>>p.s; }
template<typename S>
ostream& operator<<(ostream& os,vector<S> p) { for(auto allen:p) os<<allen<<' ';return os<<'\n'; }
template<typename S>
istream& operator>>(istream& os,vector<S> &p) { for(auto &allen:p) os>>allen;return os; }
template<typename T1,typename T2>
pair<T1,T2> operator+(pair<T1,T2> p1,pair<T1,T2> p2) { return pair<T1,T2>(p1.f+p2.f,p1.s+p2.s); }
const int mod=998244353;
const int maxn=1e5+5;
const int maxv=1e6+5;
const int inf=1ll<<60;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l,int r) {
return uniform_int_distribution<int>(l,r)(rng);
}
bool ac(vector<iint> a,vector<iint> b) {
if(SZ(a)==0||SZ(b)==0) return 0;
return are_connected(a,b);
}
std::vector<iint> longest_trip(iint N, iint D)
{
if(N==2) {
if(are_connected({0},{1})) return {0,1};
else return {0};
}
int n=N,d=D;
Vi an1={0};
Vi an2={1};
int l1=0,r1=0,l2=1,r2=1;
for(int i=2;i<n;i++) {
if(are_connected({r1},{r2})) {
reverse(ALL(an2));
for(int x:an2) an1.pb(x);
an2={i};
r1=an1.back();
l2=r2=i;
}else if(are_connected({r1},{i})){
an1.pb(i);
r1=i;
}else {
an2.pb(i);
r2=i;
}
}
#define Vii vector<iint>
if(are_connected({an1.back()},{an2[0]})) {
Vii an;
for(int x:an1) an.pb(x);
for(int x:an2) an.pb(x);
return an;
}
if(are_connected({an1[0]},{an2[0]})) {
Vii an;
reverse(ALL(an1));
for(int x:an1) an.pb(x);
for(int x:an2) an.pb(x);
return an;
}
if(are_connected({an1.back()},{an2.back()})) {
reverse(ALL(an2));
Vii an;
for(int x:an1) an.pb(x);
for(int x:an2) an.pb(x);
return an;
}
Vii s1(SZ(an1)),s2(SZ(an2));
REP(i,SZ(an1)) s1[i]=an1[i];
REP(i,SZ(an2)) s2[i]=an2[i];
// return SZ(s1)>SZ(s2)?s1:s2;
if(!are_connected(s1,s2)) return SZ(s1)>SZ(s2)?s1:s2;
int id1,id2;
{
int l1=0,r1=SZ(s1),m1;
int l2=0,r2=SZ(s2),m2;
while(l1<r1||l2<r2) {
m1=l1+r1>>1;
m2=l2+r2>>1;
Vii t1,t2,t3,t4;
for(int i=l1;i<=m1;i++) t1.pb(s1[i]);
for(int i=m1+1;i<=r1;i++) t3.pb(s1[i]);
for(int i=l2;i<=m2;i++) t2.pb(s2[i]);
for(int i=m1+1;i<=r1;i++) t4.pb(s2[i]);
if(ac(t1,t2)) r1=m1,r2=m2;
else if(ac(t3,t2)) l1=m1+1,r2=m2;
if(ac(t1,t4)) r1=m1,l2=m2+1;
else l1=m1+1,l2=m2+1;
}
id1=l1,id2=l2;
}
// {
// // assert(are_connected(s2,{id1}));
// int l=0,r=SZ(s2),m;
// while(l<r) {
// m=l+r>>1;
// Vii t;
// for(int i=l;i<=m;i++) t.pb(s2[i]);
// if(are_connected(t,{id1})) r=m;
// else l=m+1;
// }
// id2=l;
// }
// op(id1)ope(s1[id1])
// op(id2)ope(s2[id2])
Vii an;
REP(i,SZ(s1)) an.pb(s1[(id1+i+1)%SZ(s1)]);
REP(i,SZ(s2)) an.pb(s2[(id2+i)%SZ(s2)]);
return an;
}
