#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i = a;i < b;i++)
#define trav(nx, v) for(auto &nx : v)
#define all(a) begin(a), end(a)
#define sz(v) (int) v.size()

vector <int> edge[260];
bool vis[260];
int len = 0;
int path[260];
int cnt = 0;
vector <int> ans;

mt19937 rng(time(0));

void dfs(LL pos){
	vis[pos] = 1;
	
	path[cnt] = pos;
	cnt++;
	trav(nx, edge[pos]){
		if(vis[nx]) continue;
		dfs(nx);
	}
	if(cnt > sz(ans)){
		ans.resize(cnt);
		rep(i,0,cnt) ans[i] = path[i];
	}
	cnt--;
}

std::vector<int> longest_trip(int N, int D)
{
	vector <int> perm(N);
	iota(all(perm), 0);
	shuffle(all(perm), rng);
	rep(i,0,N - 2){
		int a = perm[i];
		int b = perm[i + 1];
		int c = perm[i + 2];
		if(are_connected({a}, {b, c})) {
			if(are_connected({a}, {b})) {
				edge[a].pb(b);
				edge[b].pb(a);
			} else {
				edge[a].pb(c);
				edge[c].pb(a);
			}
		} else {
			rep(j,0,N){
				if(j == b) continue;
				if(j == c) continue;
				edge[j].pb(a);
				edge[a].pb(j);
			}
		}
	}
	rep(i,0,N) shuffle(all(edge[i]), rng);
	
	return ans;
}