#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
long long n,nn[2],dh[100069],pr[100069],ex[2][100069],tmp[100069],sq[100069],zs;
bitset<1069> am[1069];
bitset<100069> vtd;
inline bool qr(vector<long long> v,vector<long long> v2)
{
long long i,j,sz,sz2;
sz=v.size();
sz2=v2.size();
for(i=0;i<sz;i++)
{
for(j=0;j<sz2;j++)
{
if(am[v[i]][v2[j]])
{
return 1;
}
}
}
return 0;
}
void dfs(long long x)
{
long long i;
vtd[x]=1;
for(i=1;i<=n;i++)
{
if(!vtd[i]&&!qr({x},{i}))
{
dh[i]=dh[x]+1;
pr[i]=x;
dfs(i);
}
}
}
bool cmdh(long long x,long long y)
{
return dh[x]<dh[y];
}
vector<int> longest_trip(int on,int d)
{
long long i,j,ii,jj,k,l,sz,e,lh,rh,md,zz;
vector<long long> cv,cv2;
vector<int> ret;
n=on;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
k=are_connected({(int)i-1},{(int)j-1});
am[i][j]=k;
am[j][i]=k;
}
}
vtd.reset();
for(ii=0;ii<2;ii++)
{
nn[ii]=0;
}
for(i=1;i<=n;i++)
{
if(!vtd[i])
{
dh[i]=0;
dfs(i);
}
e=dh[i]%2;
nn[e]++;
ex[e][nn[e]]=i;
}
for(ii=0;ii<2;ii++)
{
sort(ex[ii]+1,ex[ii]+nn[ii]+1,cmdh);
sz=0;
l=-1;
vtd.reset();
for(i=nn[ii];i;i--)
{
k=ex[ii][i];
if(l==-1)
{
l=k;
}
else if(dh[k]!=dh[l])
{
l=pr[pr[l]];
sz++;
tmp[sz]=l;
vtd[l]=1;
}
if(!vtd[k])
{
sz++;
tmp[sz]=k;
l=k;
}
}
for(i=1;i<=sz;i++)
{
ex[ii][i]=tmp[i];
}
}
zs=0;
for(i=1;i<=nn[0];i++)
{
cv.push_back(ex[0][i]);
}
for(i=1;i<=nn[1];i++)
{
cv2.push_back(ex[1][i]);
}
if(!nn[1]||!qr(cv,cv2))
{
e=nn[1]>nn[0];
for(i=1;i<=nn[e];i++)
{
zs++;
sq[zs]=ex[e][i];
}
}
else
{
for(ii=0;ii<2;ii++)
{
k=ex[0][1];
for(jj=0;jj<2;jj++)
{
l=ex[1][1];
if(!zs&&qr({k},{l}))
{
for(i=nn[0];i;i--)
{
zs++;
sq[zs]=ex[0][i];
}
for(i=1;i<=nn[1];i++)
{
zs++;
sq[zs]=ex[1][i];
}
}
reverse(ex[1]+1,ex[1]+nn[1]+1);
}
reverse(ex[0]+1,ex[0]+nn[0]+1);
}
if(!zs)
{
cv2.clear();
for(i=1;i<=nn[1];i++)
{
cv2.push_back(ex[1][i]);
}
for(ii=0;ii<2;ii++)
{
for(lh=1,rh=nn[ii];lh<=rh;)
{
md=(lh+rh)/2;
cv.clear();
for(i=1;i<=md;i++)
{
cv.push_back(ex[ii][i]);
}
if(qr(cv,cv2))
{
zz=md;
rh=md-1;
}
else
{
lh=md+1;
}
}
k=zz;
swap(k,l);
cv2.clear();
for(i=1;i<=zz;i++)
{
cv2.push_back(ex[ii][i]);
}
}
for(i=k+1;i<=nn[0];i++)
{
zs++;
sq[zs]=ex[0][i];
}
for(i=1;i<=k;i++)
{
zs++;
sq[zs]=ex[0][i];
}
for(i=l;i<=nn[1];i++)
{
zs++;
sq[zs]=ex[1][i];
}
for(i=1;i<l;i++)
{
zs++;
sq[zs]=ex[1][i];
}
}
}
for(i=1;i<=zs;i++)
{
ret.push_back(sq[i]-1);
}
return ret;
}
