#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int n;
int p[1000];
vector<int> ord;
bool visited[1000000];
vector<int> tr[1000];
bool table[1000][1000];
vector<int> nvis;
vector<int> T;
int get_vert(int node){
nvis.clear();
rep(i,0,n){
if(!visited[i])nvis.push_back(i);
}
if(nvis.empty())return -1;
if(!are_connected({node},nvis))return -1;
int lo=0;
int hi=nvis.size()-1;
while(hi-lo>0){
int mid=(hi+lo)/2;
T.clear();
rep(i,lo,mid+1)T.push_back(nvis[i]);
if(are_connected({node},T)){
hi=mid;
}else{
lo=mid+1;
}
}
return nvis[lo];
}
void DFS(int node){
visited[node]=true;
ord.push_back(node);
while(true){
int a=get_vert(node);
if(a==-1)break;
DFS(a);
tr[node].push_back(a);
tr[a].push_back(node);
p[a]=node;
}
}
bool test(int a, int b){
if(are_connected({a},{b}))return true;
return false;
}
std::vector<int> longest_trip(int N, int D)
{
n=N;
rep(i,0,n){
rep(j,0,n)table[i][j]=false;
p[i]=-1;
visited[i]=false;
tr[i].clear();
}
vector<int> ans;
rep(i,0,n){
if(!visited[i]){
ord.clear();
DFS(i);
int cnt=0;
int gt=-1;
rep(j,0,n){
if((int)tr[j].size()>=3 || (j==i && (int)tr[j].size()>=2)){
cnt++;
gt=j;
}
}
pair<int,int> bot={-1,-1};
rep(j,0,n){
if(j!=i && (int)tr[j].size()==1){
if(bot.first==-1)bot.first=j;
else{
if(bot.second!=-1)assert(false);
bot.second=j;
}
}
}
assert(cnt<=1);
assert((gt!=-1) || (bot.second==-1));
if(gt==-1){
if(ans.size()<ord.size())ans=ord;
}else{
ord.clear();
vector<int> p1;
vector<int> p2;
vector<int> p3;
int x=bot.first;
int y=bot.second;
int z=gt;
while(x!=gt){
p1.push_back(x);
x=p[x];
}
while(y!=gt){
p2.push_back(y);
y=p[y];
}
while(p[z]!=-1){
p3.push_back(p[z]);
z=p[z];
}
reverse(p3.begin(),p3.end());
trav(a,p3)ord.push_back(a);
if(p[gt]==-1){
reverse(p2.begin(),p2.end());
trav(a,p1){
ord.push_back(a);
}
ord.push_back(gt);
trav(a,p2)ord.push_back(a);
//~ rep(i,0,(int)ord.size()-1){
//~ if(!test(ord[i],ord[i+1]))assert(false);
//~ }
}else{
if(test(bot.first,p[gt])){
reverse(p2.begin(),p2.end());
trav(a,p1)ord.push_back(a);
ord.push_back(gt);
trav(a,p2)ord.push_back(a);
//~ rep(i,0,(int)ord.size()-1){
//~ if(!test(ord[i],ord[i+1]))assert(false);
//~ }
}else{
reverse(p1.begin(),p1.end());
trav(a,p2)ord.push_back(a);
ord.push_back(gt);
trav(a,p1)ord.push_back(a);
//~ rep(i,0,(int)ord.size()-1){
//~ if(!test(ord[i],ord[i+1]))assert(false);
//~ }
}
}
if(ans.size()<ord.size())ans=ord;
}
rep(j,0,n){
trav(a,tr[j]){
if(!test(a,j))assert(false);
}
tr[j].clear();
p[j]=-1;
}
}
}
return ans;
}
