// Q = O(2N)
#include "longesttrip.h"
#include <bits/stdc++.h>
#define ll long long
#define SZ(X) (int)(X.size())
using namespace std;

int nodeNum, density;
vector <int> chain[2];
vector <int> seg;
vector <int> ans;

void reset(){
    chain[0].clear();
    chain[1].clear();
    seg.clear();
    ans.clear();
}

void print(vector <int> & v){
    for (int x : v)
        cout << x << " ";
    cout << "\n";
}

/*bool are_connected(vector <int> A, vector <int> B){
    print(A);
    print(B);
    bool a;
    cin >> a;
    return a;
}*/

void constructVect(vector <int> & source, vector <int> & loc, int le, int ri, bool clearV){
    if (clearV) loc.clear();
    for (int i = le; i < ri; i++)
        loc.push_back(source[i]);
}

bool connectedEdges(){
    vector <int> a;
    vector <int> b;
    a.push_back(chain[0][0]);
    if (SZ(chain[0]) > 1) a.push_back(chain[0].back());
    b.push_back(chain[1][0]);
    if (SZ(chain[1]) > 1) b.push_back(chain[1].back());
    return are_connected(a, b);
}

vector <int> longest_trip(int N, int D){
    nodeNum = N;
    density = D;
    reset();
    chain[0].push_back(0);
    for (int i = 1; i < nodeNum; i++){
        if (are_connected({chain[0].back()}, {i})) { // connected to first chain
            chain[0].push_back(i);
            if (!chain[1].empty() && are_connected({chain[1].back()}, {i})){ // connected to both chains
                while (!chain[1].empty()){
                    chain[0].push_back(chain[1].back());
                    chain[1].pop_back();
                }
            }
        }
        else chain[1].push_back(i); // connected only to second chain
    }
    if (chain[0].empty()) return chain[1];
    if (chain[1].empty()) return chain[0];
    if (!are_connected(chain[0], chain[1])){ // two separate components
        if (SZ(chain[0]) >= SZ(chain[1])) return chain[0];
        else return chain[1];
    }
    
    if (connectedEdges()){ // chains are connected by the edges
        for (int i : {0, SZ(chain[0])-1}){
            for (int j : {0, SZ(chain[1])-1}){
                if (are_connected({chain[0][i]}, {chain[1][j]})){
                    if (i == 0) reverse(chain[0].begin(), chain[0].end());
                    if (j != 0) reverse(chain[1].begin(), chain[1].end());
                    for (int x : chain[0]) ans.push_back(x);
                    for (int x : chain[1]) ans.push_back(x);
                    return ans;
                }
            }
        }
        assert(0 == 1); // not supposed to get here
    }
    
    // chains are not connected by edges
    int le = 0, ri = SZ(chain[0])-1, mid; // bin search chain[0]
    while (le < ri){
        mid = (le+ri)/2;
        constructVect(chain[0], seg, 0, mid+1, true);
        if (are_connected(seg, chain[1])) ri = mid;
        else le = mid+1;
    }
    int res = le;
    constructVect(chain[0], ans, res+1, SZ(chain[0]), false);
    constructVect(chain[0], ans, 0, res+1, false);
    
    le = 0;
    ri = SZ(chain[1])-1;
    while (le < ri){
        mid = (le+ri)/2;
        constructVect(chain[1], seg, 0, mid+1, true);
        if (are_connected({chain[0][res]}, seg)) ri = mid;
        else le = mid+1;
    }
    constructVect(chain[1], ans, le, SZ(chain[1]), false);
    constructVect(chain[1], ans, 0, le, false);
    return ans;
}
/*
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    auto vect = longest_trip(3, 3);
    print(vect);
    cout << "done!\n";
    
    return 0;
}
*/