#include "longesttrip.h"

#include <cstring>
#include <cassert>
#include <algorithm>

using namespace std;

const int maxn = 300;

bool vis[maxn], vis2[maxn];
int p[maxn];
bool g[maxn][maxn];
vector<int> t[maxn];
int n;
int component_size = 0;

void dfs(int u){
    vis[u] = true;
    ++component_size;
    for (int i = 0;i < n;i++){
        if (g[u][i] && !vis[i]){
            p[i] = u;
            t[u].push_back(i);
            t[i].push_back(u);
            dfs(i);
        }
    }
}

vector<int> path;

void find_path(int u){
    vis[u] = true;
    path.push_back(u);
    for (auto v : t[u]){
        if (!vis[v]){
            find_path(v);
            return;
        }
    }
}

void dfs2(int u){
    vis[u] = true;
    for (auto v : t[u]){
        if (!vis[v]){
            p[v] = u;
            dfs2(v);
        }
    }
}

std::vector<int> longest_trip(int N, int D)
{
    n = N;
    for (int i = 0;i < n;i++){
        t[i].clear();
        g[i][i] = false;
        for (int j = i+1;j < n;j++){
            bool has_edge = are_connected(vector<int>(1,i),vector<int>(1,j));
            g[i][j] = g[j][i] = has_edge;
        }
    }
    memset(vis,false,sizeof vis);
    int max_size = -1;
    int max_id = 0;
    for (int i = 0;i < n;i++){
        if (!vis[i]){
            component_size = 0;
            dfs(i);
            if (component_size > max_size){
                max_size = component_size;
                max_id = i;
            }
        }
    }
    // Find dfs tree from vertex max_id
    memset(vis,false,sizeof vis);
    for (int i = 0;i < n;i++){
        t[i].clear();
    }
    dfs(max_id);
    int max_deg = 0;
    for (int i = 0;i < n;i++){
        if (vis[i]) max_deg = max(max_deg, (int)t[i].size());
    }
    assert(max_deg <= 3);
    path.clear();
    if (max_deg <= 2){
        // Starting from a deg one vertex then go from there
        memset(vis,false,sizeof vis);
        for (int i = 0;i < n;i++){
            if (t[i].size() == 1){
                find_path(i);
                return path;
            }
        }
    }
    else{
        // The vertex with max degree 3 shall be unique, and there must be 3 deg 1 vertices
        int root = 0;
        for (int i = 0;i < n;i++){
            if (t[i].size() == 3){
                assert(root == 0);
                root = i;
            }
        }
        assert(root != 0);
        memset(vis,false,sizeof vis);
        dfs2(root);

        int deg_1[4];
        int count_1 = 0;
        for (int i = 0;i < n;i++){
            if (t[i].size() == 1){
                deg_1[++count_1] = i;
            }
        }
        assert(count_1 == 3);

        for (int i = 1;i <= 3;i++){
            for (int j = i+1;j <= 3;j++){
                if (g[deg_1[i]][deg_1[j]]){
                    memset(vis,false,sizeof vis);
                    find_path(deg_1[6-i-j]);
                    for (int k = 1;k <= 3;k++){
                        if (!vis[deg_1[k]]){
                            int cur = deg_1[k];
                            while (cur != root){
                                path.push_back(cur);
                                cur = p[cur];
                            }
                            return path;
                        }
                    }
                }
            }
        }
    }
}