#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<int> p;
int cnt = 0;
void dfs(int node,bool b){
    if(b) p.push_back(node);
    vis[node] = 1;
    cnt ++;
    for(auto ch : adj[node]){
        if(vis[ch]) continue;
        dfs(ch,!b);
        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;
    }
    map<pair<int,int>,bool> edge;
    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;
                }
                else {
                    edge[{i,j}] = 1;
                    edge[{j,i}] = 1;
                }
            }
        }
        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;
        cnt = 0;        
        dfs(i,1);
        assert(cnt!=3);
        if(cnt%2==0 && cnt>4) dfs(nxt(i),1);
    }
    for(int i=1;i<p.size();i++){
        if(edge.count({p[i],p[i-1]})) continue;
        assert(0);
    }
    assert(p.size()>=n/2+n%2);
    return p;
}