#include "fun.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int MAXN = 505;
vector<int> con[MAXN];
bool used[MAXN];
pair<int, int> find_depth(int curr, int par){ // depth, node
pair<int, int> res = {-1, -1};
for (auto i : con[curr]){
if (i == par or used[i]) continue;
pair<int, int> b = find_depth(i, curr);
if (b.first > res.first) res = b;
}
if (res.first == -1)
return {1, curr};
return {res.first + 1, res.second};
}
pair<int, int> find_remove(int start){ // node1, node2
pair<int, int> b1 = {-1, -1}, b2 = {-1, -1};
for (auto i : con[start]){
if (used[i]) continue;
pair<int, int> res = find_depth(i, start);
if (b1.first == -1) b1 = res;
else if (b2.first == -1 and b2.second != res.second and b1.second != res.second) b2 = res;
else if (res.first > b1.first and b2.second != res.second and b1.second != res.second) b2 = b1, b1 = res;
else if (res.first > b2.first and b2.second != res.second and b1.second != res.second) b2 = res;
}
if (b2.first == -1)
b2.second = start;
return {b1.second, b2.second};
}
void make_tree(int n){
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (hoursRequired(i, j) == 1)
con[i].push_back(j), con[j].push_back(i);
}
std::vector<int> createFunTour(int n, int Q) {
vector<int> res;
make_tree(n);
int total = n;
while (total > 2){
int start;
for (int i = 0; i < n; i++)
if (!used[i]) {start = i; break;}
pair<int, int> t = find_remove(start);
total -= 2;
used[t.first] = used[t.second] = true;
res.push_back(t.first), res.push_back(t.second);
}
for (int i = 0; i < n; i++)
if (!used[i]) res.push_back(i);
return res;
}
