/*
ID: Victor Chen [mail_vi1]
PROG: Longest Trip
LANG: C++
*/

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include "longesttrip.h"
#include <cassert>

using namespace std;

typedef long long ll;

const int Maxn = 300;

class Graph
{
    public:
        int cnt, head[Maxn+10];
        struct Edge
        {
            int to, nxt;
        }p[2*Maxn+10];

        int root;
        int dep[Maxn+10], fa[Maxn+10];

        void AddEdge(int x, int y)
        {
            cnt++;
            p[cnt].to = y;

            p[cnt].nxt = head[x];
            head[x] = cnt;
        }

        void dfs(int x)
        {
            for(int i=head[x]; i!=0; i=p[i].nxt)
                if(dep[p[i].to] == 0)
                {
                    dep[p[i].to] = dep[x] + 1;
                    fa[p[i].to] = x;
                    dfs(p[i].to);
                }
        }

        void clear()
        {
            cnt = 0;
            memset(head, 0, sizeof(head));
        }

        void init(int x)
        {
            root = x;
            memset(dep, 0, sizeof(dep));
            dep[root] = 1;
            fa[root] = 0;

            dfs(root);
        }
}g;

int bg1, ed1, bg2, ed2;

vector<int> vint(int k)
{
    vector<int> ret;
    ret.clear();
    ret.push_back(k);
    return ret;
}
vector<int> v2int(int x, int y)
{
    vector<int> ret;
    ret.clear();
    ret.push_back(x);

    if(x != y)
        ret.push_back(y);
    return ret;
}

vector<int> ret;
void dfs(int x)
{
    ret.push_back(x);
    for(int i=g.head[x]; i!=0; i=g.p[i].nxt)
        if(g.dep[g.p[i].to] == g.dep[x] + 1)
            dfs(g.p[i].to);
}

int k1, k2;

vector<int> test;
vector<int> seq1, seq2;
void dfs_seq1(int x)
{
    seq1.push_back(x);
    for(int i=g.head[x]; i!=0; i=g.p[i].nxt)
        if(g.dep[g.p[i].to] == g.dep[x] + 1)
            dfs_seq1(g.p[i].to);
}
void dfs_seq2(int x)
{
    seq2.push_back(x);
    for(int i=g.head[x]; i!=0; i=g.p[i].nxt)
        if(g.dep[g.p[i].to] == g.dep[x] + 1)
            dfs_seq2(g.p[i].to);
}

void print(vector<int> v)
{
    for(int i=0; i<v.size(); i++)
        printf("%d ", v[i]);
    printf("\n");
}

bool are_connected(vector<int> A, vector<int> B);

vector<int> longest_trip(int N, int D)
{
    g.clear(); ret.clear();

    bg1 = ed1 = 0, bg2 = ed2 = 1;
    for(int i=2; i<N; i++)
    {
        bool flag = are_connected(vint(i), vint(ed1));

        // print(vint(i));

        if(flag)
        {
            g.AddEdge(ed1, i);
            g.AddEdge(i, ed1);
            ed1 = i;
        }
        else
        {
            flag = are_connected(vint(i), vint(ed2));
            if(flag)
            {
                g.AddEdge(ed2, i);
                g.AddEdge(i, ed2);
                ed2 = i;
            }
            else
            {
                g.AddEdge(ed1, ed2);
                g.AddEdge(ed2, ed1);
                ed1 = bg2;
                bg2 = ed2 = i;
            }
        }
    }

    // assert(false);

    bool flag = are_connected(v2int(bg1, ed1), v2int(bg2, ed2));

    if(flag == true)
    {
        if(are_connected(vint(bg1), vint(bg2)))
        {
            g.AddEdge(bg1, bg2);
            g.AddEdge(bg2, bg1);

            g.init(ed1);
            dfs(ed1);
        }
        else if(are_connected(vint(bg1), vint(ed2)))
        {
            g.AddEdge(bg1, ed2);
            g.AddEdge(ed2, bg1);

            g.init(ed1);
            dfs(ed1);
        }
        else if(are_connected(vint(ed1), vint(bg2)))
        {
            g.AddEdge(ed1, bg2);
            g.AddEdge(bg2, ed1);

            g.init(bg1);
            dfs(bg1);
        }
        else
        {
            g.AddEdge(ed1, ed2);
            g.AddEdge(ed2, ed1);

            g.init(bg1);
            dfs(bg1);
        }
    }
    else
    {
        seq1.clear(); seq2.clear();

        g.init(bg1);
        dfs_seq1(bg1);
        g.init(bg2);
        dfs_seq2(bg2);

        // printf("Check: %d %d\n", bg1, bg2);
        // print(seq1);
        // print(seq2);

        if(are_connected(seq1, seq2) == false)
        {
            if(seq1.size() > seq2.size())
                return seq1;
            else
                return seq2;
        }

        // print(seq1);
        // print(seq2);

        int l = 0, r = seq1.size()-1;
        while(l != r)
        {
            int mid = (l+r)/2;

            test.clear();
            for(int i=l; i<=mid; i++)
                test.push_back(seq1[i]);
            
            if(are_connected(test, seq2))
                r = mid;
            else
                l = mid + 1;
        }
        k1 = l;

        assert(are_connected(vint(seq1[k1]), seq2));

        l = 0, r = seq2.size()-1;
        while(l != r)
        {
            int mid = (l+r)/2;

            test.clear();
            for(int i=l; i<=mid; i++)
                test.push_back(seq2[i]);
            
            if(are_connected(test, seq1))
                r = mid;
            else
                l = mid + 1;
        }
        k2 = l;

        assert(are_connected(vint(seq2[k1]), seq1));

        for(int i=k1+1; i<seq1.size(); i++) ret.push_back(seq1[i]);
        for(int i=0; i<=k1; i++) ret.push_back(seq1[i]);
        for(int i=k2; i<seq2.size(); i++) ret.push_back(seq2[i]);
        for(int i=0; i<k2; i++) ret.push_back(seq2[i]);
    }

    // return vint(1);

    return ret;
}

// int main()
// {
//     return 0;
// }