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