#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/int_alias.hpp"
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 2 "library2/utility/rec_lambda.hpp"
template <class F> class RecursiveLambda {
F f;
public:
explicit constexpr RecursiveLambda(F &&f_) : f(std::forward<F>(f_)) {}
template <class... Args> constexpr auto operator()(Args &&...args) const {
return f(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F &&f) {
return RecursiveLambda<F>(std::forward<F>(f));
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 2 "library2/utility/setmax.hpp"
template <typename T> bool setmax(T &lhs, const T &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
#line 7 "paper.cpp"
int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);
std::vector<int> createFunTour(int N, int Q) {
std::vector<std::vector<int>> Tree(N);
for (const int i : rep(N)) {
for (const int j : rep(i + 1, N)) {
if (hoursRequired(i, j) == 1) {
Tree[i].push_back(j);
Tree[j].push_back(i);
}
}
}
auto dfs = rec_lambda([&](auto &&f, const int v, const int p, std::vector<int> &dist) -> void {
for (const int t : Tree[v]) {
if (t == p) {
continue;
}
dist[t] = dist[v] + 1;
f(t, v, dist);
}
});
auto find_diameterpoint = [&]() {
std::vector<int> dist1(N), dist2(N);
dfs(0, N, dist1);
const auto max_idx = (int)(std::max_element(dist1.begin(), dist1.end()) - dist1.begin());
dfs(max_idx, N, dist2);
return std::make_pair(max_idx,
(int)(std::max_element(dist2.begin(), dist2.end()) - dist2.begin()));
};
const auto [a, b] = find_diameterpoint();
std::vector<bool> used(N);
used[a] = used[b] = true;
std::vector<int> ret(N);
ret[0] = a, ret[1] = b;
int last = b;
for (const int i : rep(N - 2)) {
std::vector<int> dist(N);
dfs(last, N, dist);
int max = 0, max_idx = 0;
for (const int i : rep(N)) {
if (not used[i]) {
if (setmax(max, dist[i])) {
max_idx = i;
}
}
}
used[max_idx] = true;
ret[i + 2] = max_idx;
last = max_idx;
}
return ret;
}
/*
static void wrongAnswer(std::string message) {
printf("WA: %s\n", message.c_str());
exit(0);
}
namespace tree_helper {
static int N;
static int logN;
static std::vector<std::vector<int>> parent;
static std::vector<int> depth;
static std::vector<int> subtree_size;
static void dfs(const std::vector<std::vector<int>> &adj_list, int current_node, int parent_node) {
parent[0][current_node] = parent_node;
subtree_size[current_node] = 1;
for (int i = 0; i < static_cast<int>(adj_list[current_node].size()); ++i) {
const int next_node = adj_list[current_node][i];
if (next_node != parent_node) {
depth[next_node] = depth[current_node] + 1;
dfs(adj_list, next_node, current_node);
subtree_size[current_node] += subtree_size[next_node];
}
}
}
static void initializeTree(const std::vector<std::vector<int>> &adj_list) {
N = static_cast<int>(adj_list.size());
depth = std::vector<int>(N, 0);
subtree_size = std::vector<int>(N, 0);
for (logN = 0; (1 << logN) < N; ++logN) {
}
parent = std::vector<std::vector<int>>(logN, std::vector<int>(N, 0));
dfs(adj_list, 0, 0);
for (int i = 1; i < logN; ++i) {
for (int j = 0; j < N; ++j) {
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
}
static int getLowestCommonAncestor(int X, int Y) {
if (depth[X] < depth[Y]) {
std::swap(X, Y);
}
for (int i = logN - 1; i >= 0; --i) {
if (depth[parent[i][X]] >= depth[Y]) {
X = parent[i][X];
}
}
if (X == Y) {
return X;
}
for (int i = logN - 1; i >= 0; --i) {
if (parent[i][X] != parent[i][Y]) {
X = parent[i][X];
Y = parent[i][Y];
}
}
return parent[0][X];
}
static int getDistance(int X, int Y) {
return depth[X] + depth[Y] - 2 * depth[getLowestCommonAncestor(X, Y)];
}
static int attractionsBehind(int X, int Y) {
if (X == Y) {
return N;
}
for (int i = logN - 1; i >= 0; --i) {
if (depth[parent[i][X]] > depth[Y]) {
X = parent[i][X];
}
}
if (Y == parent[0][X]) {
return N - subtree_size[X];
}
return subtree_size[Y];
}
static void checkFunTour(const std::vector<int> &fun_tour) {
if (static_cast<int>(fun_tour.size()) != N) {
wrongAnswer("Invalid size");
}
std::vector<bool> visited_attractions(N, false);
for (int i = 0; i < N; ++i) {
if (fun_tour[i] < 0 || fun_tour[i] >= N) {
wrongAnswer("Invalid index");
}
if (visited_attractions[fun_tour[i]]) {
wrongAnswer("Repeated index");
}
visited_attractions[fun_tour[i]] = true;
}
int last_travel_time = getDistance(fun_tour[0], fun_tour[1]);
for (int i = 2; i < N; ++i) {
int travel_time = getDistance(fun_tour[i - 1], fun_tour[i]);
if (travel_time > last_travel_time) {
wrongAnswer("Tour is not fun");
}
last_travel_time = travel_time;
}
}
} // namespace tree_helper
static int N, Q;
int hoursRequired(int X, int Y) {
if (--Q < 0) {
wrongAnswer("Too many queries");
}
if (X < 0 || X >= N || Y < 0 || Y >= N) {
wrongAnswer("Invalid index");
}
return tree_helper::getDistance(X, Y);
}
int attractionsBehind(int X, int Y) {
if (--Q < 0) {
wrongAnswer("Too many queries");
}
if (X < 0 || X >= N || Y < 0 || Y >= N) {
wrongAnswer("Invalid index");
}
return tree_helper::attractionsBehind(X, Y);
}
int main() {
assert(2 == scanf("%d %d", &N, &Q));
std::vector<std::vector<int>> adj_list(N);
for (int i = 0; i < N - 1; ++i) {
int A, B;
assert(2 == scanf("%d %d", &A, &B));
adj_list[A].push_back(B);
adj_list[B].push_back(A);
}
tree_helper::initializeTree(adj_list);
std::vector<int> fun_tour = createFunTour(N, Q);
tree_helper::checkFunTour(fun_tour);
for (int i = 0; i < N; ++i) {
printf("%d%c", fun_tour[i], " \n"[i == N - 1]);
}
return 0;
}
*/
