antichainって$x \perp y \iff \lnot \exists z. z \le x \land z \le y$として$\forall x, y \in A. x \ne y \to x \perp y$だと思ってたけど、$\forall x, y \in A. x \ne y \to \lnot (x \le y) \land \lnot (y \le x)$もそう言うらしい。それはそう。どうせ列に対してでなくて集合に対する性質だけど。

## implementation

#include <algorithm>
#include <cstdio>
#include <numeric>
#include <random>
#include <set>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

default_random_engine gen((random_device())());

vector<int> solve(int n, vector<vector<int> > const & g) {
repeat (i, n) {
if (g[i].size() == n - 1) {
return vector<int>(); // star
}
}
vector<set<int> > g_set(n);
repeat (i, n) {
for (int j : g[i]) {
g_set[i].insert(j);
}
}
while (true) {
vector<int> rank(n);
repeat (i, n) {
rank[i] = g[i].size() + uniform_int_distribution<int>(-2, 4)(gen);
}
vector<int> xs(n);
whole(iota, xs, 0);
whole(sort, xs, [&](int i, int j) { return rank[i] > rank[j]; });
vector<int> ys;
swap(xs[0], xs.back());
ys.push_back(xs.back());
xs.pop_back();
while (not xs.empty()) {
int i = 0;
for (; i < xs.size(); ++ i) {
if (not g_set[ys.back()].count(xs[i])) {
swap(xs[i], xs.back());
ys.push_back(xs.back());
xs.pop_back();
i = -1;
break;
}
}
if (i == xs.size()) {
ys.clear();
break;
}
}
if (not ys.empty()) {
return ys;
}
}
}

int main() {
int testcases; scanf("%d", &testcases);
while (testcases --) {
int n; scanf("%d", &n);
vector<vector<int> > g(n);
repeat (i, n - 1) {
int x, y; scanf("%d%d", &x, &y); -- x; -- y;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> result = solve(n, g);
if (result.empty()) {
printf("-1\n");
} else {
repeat (i, n) {
printf("%d%c", result[i] + 1, i + 1 == n ? '\n' : ' ');
}
}
}
return 0;
}