#include "longesttrip.h"

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

using namespace std;

const int maxn = 300;

int col[maxn];
bool vis[maxn];
int p[maxn];
vector<int> t[maxn];
int n;
int component_size = 0;
int components = 0;

int find_a_nonvis_edge(int u){
    vector<int> candidates;
    for (int i = 0;i < n;i++){
        if (!vis[i]){
            candidates.push_back(i);
        }
    }
    if (candidates.size() == 0){
        return -1;
    }
    if (!are_connected(candidates, vector<int>(1,u))){
        return -1;
    }
    else{
        // half the size of candidates by 2 each time
        while ((int)candidates.size() > 1){
            vector<int> first_half;
            for (int i = 0;i < candidates.size() / 2;i++){
              first_half.push_back(candidates[i]);
            }
            if (are_connected(first_half, vector<int>(1,u))){
                candidates = first_half;
            }
            else{
                vector<int> t;
                for (int i = candidates.size()/2;i < candidates.size();i++){
                  t.push_back(candidates[i]);
                }
                candidates = t;
            }
        }
        return candidates[0];
    }
}

void dfs(int u){
    vis[u] = true;
    col[u] = components;
    ++component_size;
    int i;
    while ((i = find_a_nonvis_edge(u)) != -1){
            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();
        col[i] = -1;
    }
    memset(vis,false,sizeof vis);
    int max_size = -1;
    int max_id = 0;
    components = 0;

    for (int i = 0;i < n;i++){
        if (!vis[i]){
            component_size = 0;
            ++components;
            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);
    memset(p,0,sizeof p);

    int max_deg = 0;
    for (int i = 0;i < n;i++){
        if (col[i] == col[max_id]) 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 && col[i] == col[max_id]){
                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 && col[i] == col[max_id]){
                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 && col[i] == col[max_id]){
                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 (are_connected(vector<int>(1,deg_1[i]), vector<int>(1,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;
                        }
                    }
                }
            }
        }
    }
}