#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;
ll fpow(ll a,ll b,ll m)
{
if(!b) return 1;
ll tmp=1;
for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)
#include "longesttrip.h"
int has[300][300];
vector<int> ed[300];
bool vis[300];
int par[300];
int deg[300],cnt[300];
int n;
vector<int> longest_trip(int N,int D)
{
n=N;
rep(i,n)
{
rep(j,n)
{
has[i][j]=-1;
}
ed[i].clear();
vis[i]=0;
par[i]=-1;
deg[i]=cnt[i]=0;
}
vector<int> ret;
if(D==3)
{
rep(i,n) ret.pb(i);
return ret;
}
vector<int> v1={0},v2;
bool has=1;
rep1(i,n-1)
{
if(are_connected({v1.back()},{i}))
{
v1.pb(i);
has=1;
}
else if(has==0)
{
v2.pb(i);
}
else
{
if(v2.empty()||are_connected({v2.back()},{i}))
{
v2.pb(i);
has=0;
}
else
{
reverse(v2.begin(),v2.end());
for(int x:v2) v1.pb(x);
v2={i};
has=1;
}
}
}
if(v1.size()<v2.size()) swap(v1,v2);
if(v2.empty()) return v1;
if(!are_connected(v1,v2)) return v1;
if(are_connected({v1[0]},{v2[0]}))
{
reverse(v2.begin(),v2.end());
for(int x:v1) v2.pb(x);
return v2;
}
if(are_connected({v1.back()},{v2[0]}))
{
for(int x:v2) v1.pb(x);
return v1;
}
int l=0,r=(int)v1.size()-1;
while(l<r)
{
int mid=l+r>>1;
vector<int> tmp;
rep(i,mid+1) tmp.pb(v1[i]);
if(are_connected(tmp,{v2[0]})) r=mid;
else l=mid+1;
}
reverse(v2.begin(),v2.end());
for(int i=l;i<v1.size();i++) v2.pb(v1[i]);
rep(i,l) v2.pb(v1[i]);
return v2;
}
