#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
const int mxN = 261;
#define all(x) x.begin(), x.end()
vector<int> adj[mxN];
deque<int> path[2][mxN];
//set<pair<int, int>> current_edges;
/*
bool are_connected(vector<int> a, vector<int> b){
int u = a[0], v = b[0];
if(current_edges.find({u, v}) != current_edges.end()) return 1;
if(current_edges.find({v, u}) != current_edges.end()) return 1;
return 0;
}
*/
vector<int> longest_trip(int N, int D)
{
vector<int> in(N + 5, 0), ans;
for(int i = 0; i < N; ++i) adj[i].clear(), path[0][i].clear(), path[1][i].clear(), in[i] = 0;
if(D == 3){
for(int i = 0; i < N; ++i) ans.push_back(i);
return ans;
}
for(int i = 0; i < N; ++i){
for(int j = i + 1; j < N; ++j){
bool edge = are_connected({i}, {j});
if(edge){
adj[j].push_back(i);
in[i] += 1;
}
}
}
queue<int> que;
for(int i = 0; i < N; ++i){
if(in[i] == 0) que.push(i);
path[0][i] = path[1][i] = {i};
}
while((int) que.size()){
auto tp = que.front();
que.pop();
for(auto v : adj[tp]){
if((int) path[0][v].size() < (int) path[0][tp].size() + 1){
swap(path[0][v], path[1][v]);
path[0][v] = path[0][tp];
path[0][v].push_front(v);
} else if((int) path[1][v].size() < (int) path[0][tp].size() + 1){
path[1][v] = path[0][tp];
path[1][v].push_front(v);
} else if((int) path[1][v].size() < (int) path[1][tp].size() + 1){
path[1][v] = path[1][tp];
path[1][v].push_front(v);
}
if(--in[v] == 0) que.push(v);
}
}
int len = 0;
for(int i = 0; i < N; ++i) {
len = max(len, (int) path[0][i].size() + (int) path[1][i].size() - 1);
}
for(int i = 0; i < N; ++i){
if(len == ((int) path[0][i].size() + (int) path[1][i].size() - 1)) {
for(int j = (int) path[1][i].size() - 1; j >= 1; --j) ans.push_back(path[1][i][j]);
for(auto it : path[0][i]) ans.push_back(it);
break;
}
}
return ans;
}
/*
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0, u, v; i < m; ++i){
cin >> u >> v;
current_edges.insert({u, v});
}
vector<int> ans = longest_trip(n, 0);
for(auto v : ans) cout << v << "\n";
return 0;
}
*/
