#include<bits/stdc++.h>
#define fz1(i,n) for((i)=1;(i)<=(n);(i)++)
#define fz(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for((i)=(a);(i)>=(b);(i)--)
#define fd1(i,n) for((i)=(n);(i)>=1;(i)--)
#define fz0k(i,n) for((i)=0;(i)<(n);(i)++)
#define fz0g(i,n) for((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for((i)=(n);(i)>=0;(i)--)
using namespace std;
//static std::vector<std::vector<int>> U;
#include "longesttrip.h"
int n,m,i,j,rt;
mt19937 rnd(time(NULL));
vector<int> p;
bool query(std::vector<int> A, std::vector<int> B)
{
	for(int &u:A) u=p[u];
	for(int &u:B) u=p[u];
	return are_connected(A,B);
}
std::vector<int> _longest_trip(int N, int D)
{
	n=N;
	p.resize(n);fz0k(i,n)p[i]=i;
	fz1(i,n-1) swap(p[i],p[rnd()%(i+1)]);
	vector<int> v1,v2;rt=0;
	
	vector<int> cur={rt};int u;
	fz0k(u,n)if(u!=rt){
		if(query({u},{cur.back()})){
			cur.push_back(u);
			continue;
		}
		else if(cur.back()==rt){
			v2.push_back(u);
			continue;
		}
		if(v2.size()>80||!query({rt},{u})){
			v2.push_back(u);
			continue;
		}
		int pos=-1;fz0k(i,cur.size())if(cur[i]==rt)pos=i;
		if(query({u},{cur[pos-1]})){
			cur.insert(cur.begin()+pos,u);
			continue;
		}
//		assert(U[max(cur[pos-1],cur.back())][min(cur[pos-1],cur.back())]);
		vector<int> nxt;
		fz0k(i,pos) nxt.push_back(cur[i]);
		fd(i,cur.size()-1,pos) nxt.push_back(cur[i]);
		nxt.push_back(u);
		cur=nxt;
//		for(i=1;i<cur.size();i++) assert(U[max(cur[i],cur[i-1])][min(cur[i],cur[i-1])]);
	}

	v1=cur;
	if(v2.empty()||!query(v1,v2)){
		if(v1.size()>=v2.size()){
			return v1;
		}
		else return v2;
	}
	int l=-1,r=((int)v1.size())-2,sx=v1.size()-1,mid;
	while(l<r){
		mid=(l+r+1)/2;
		vector<int> tmp;fz0g(i,mid) tmp.push_back(v1[i]);
		if(query(tmp,v2)) r=mid-1,sx=mid;
		else l=mid;
	}
	l=-1;r=((int)v2.size())-2;int sy=v2.size()-1;
	while(l<r){
		mid=(l+r+1)/2;
		vector<int> tmp;fz0g(i,mid) tmp.push_back(v2[i]);
		if(query(tmp,{v1[sx]})) r=mid-1,sy=mid;
		else l=mid;
	}
	swap(v2[0],v2[sy]);

	if(query({v1.back()},{v2[0]})){
		for(int u:v2) v1.push_back(u);
		cerr<<"A\n";
		return v1;
	}
	if(query({v1[0]},{v2[0]})){
		reverse(v1.begin(),v1.end());
		for(int u:v2) v1.push_back(u);
		cerr<<"B\n";
		return v1;
	}
	cerr<<"C\n";
	reverse(v2.begin(),v2.end());
	for(i=sx;i<v1.size();i++) v2.push_back(v1[i]);
	for(i=0;i<sx;i++) v2.push_back(v1[i]);
	return v2;
}
std::vector<int> longest_trip(int N, int D)
{
	vector<int> ans=_longest_trip(N,D);
	for(int &u:ans) u=p[u];
	return ans;
}