#include "longesttrip.h"

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

using namespace std;

const int maxn = 300;

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

int recursive_find(int u,vector<int> candidates){
    if (candidates.size() == 1){
        return candidates[0];
    }
    // Double each time
    int i = 0;
    for (;(1 << i) < candidates.size();i++){
        // Search for first [1 << i] elements
        vector<int> t;
        for (int j = (i == 0) ? 0 : (1 << (i-1));j < (1 << i);j++){
            t.push_back(candidates[j]);
        }
        if (are_connected(t, vector<int>(1,u))){
            return recursive_find(u, t);
        }
        else{
          for (int i = 0;i < t.size();i++){
              for (int j = i+1;j < t.size();j++){
                  g[t[i]][t[j]] = g[t[j]][t[i]] = true;
              }
          }
        }
    }
    vector<int> t;
    for (int j = (1 << i);j < candidates.size();j++){
        t.push_back(candidates[j]);
    }
    return recursive_find(u, t);
}

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 (g[u][i]) return i;
        }
    }
    if (candidates.size() == 0){
        return -1;
    }
    if (!are_connected(candidates, vector<int>(1,u))){
        // no between u and candidates; candidates form a clique
        for (int i = 0;i < candidates.size();i++){
            for (int j = i+1;j < candidates.size();j++){
                g[candidates[i]][candidates[j]] = g[candidates[j]][candidates[i]] = true;
            }
        }
        return -1;
    }
    else{
        return recursive_find(u, candidates);
    }
}

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++){
      for (int j = 0;j < n;j++){
        g[i][j] = false;
      }
        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;
                        }
                    }
                }
            }
        }
    }
}