#include <bits/stdc++.h>
#include "longesttrip.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
vector<vector<int>> adj;
vector<bool> vis;
vector<vector<int>> p;
vector<int> pp;
void dfs(int node){
    pp.push_back(node);
    vis[node] = 1;
    for(auto ch : adj[node]){
        if(vis[ch]) continue;
        dfs(ch);
        break;
    }
}
vector<int> longest_trip(int n, int d)
{
    if(d == 3) {
        vector<int> ans(n);
        iota(ans.begin(),ans.end(),0);
        return ans;
    }
    if(d == 2){
        vector<int> a;
        vector<int> b;
        vector<bool> rem(n,1);
        vector<int> ans;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(!are_connected({i},{j})) {
                    a.push_back(i);
                    b.push_back(j);
                    rem[i] = 0;
                    rem[j] = 0;
                }
            }
        }
        for(auto i : a) ans.push_back(i);
        for(int i=0;i<n;i++) if(rem[i]) ans.push_back(i);
        for(auto i : b) ans.push_back(i);
        return ans;
    }
    adj.clear();
    adj.resize(n);    
    vis.clear();
    vis.resize(n);
    p.clear();
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        pp.clear();
        dfs(i);
        p.push_back(pp);
    }
    vector<int> ans;
    for(auto a : p){
        vector<bool> vis(n);
        int i = 0;
        while(!vis[i]){
            vis[i] = 1;
            ans.push_back(a[i]);
            if(i == 0 && i+2 == a.size()-1) break;
            i += 2;
            if(i>=a.size()) i -= a.size();
        }
        if(a.size()>4 && a.size()%2==0){
            i = 1;
            while(!vis[i]){
                vis[i] = 1;
                ans.push_back(a[i]);
                if(i == 0 && i+2 == a.size()-1) break;
                i += 2;
                if(i>=a.size()) i -= a.size();
            }
        }
    }
    return ans;
}