CF2107D Apple Tree Traversing

有一棵 $n$ 个点的苹果树，每个结点上有一棵苹果。你有一张白纸。 你将要在苹果树上穿梭，重复做以下事情直到苹果树上没有苹果： - 选择一条路径 $(u,v)$，满足这条路径上所有点上都有苹果。 - 拿走这条路径上的所有苹果，设你这次拿了 $d$ 个苹果，在你的纸上依次写下三个数字 $d$，$u$ 和 $v$。 称结束后你的纸上的数字构成的数列为 $a$。输出可能的字典序最大的 $a$。

多组数据，第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。 对于每组数据，第一行一个整数 $n(1\le n\le 1.5\times 10^5)$。\ 接下来 $n-1$ 行，每行两个数字表示树上的一条边。 保证一个测试点中 $\sum n\le 1.5\times 10^5$。

每组数据输出一行，为可能的字典序最大的 $a$。可以证明 $a$ 的长度 $\le 3\times n$。

在第一组数据中，我们进行以下操作： - 选择路径 $(4,3)$，拿走结点 $1,3,4$ 上面的苹果，在纸上写下 $3,4,3$。 - 选择路径 $(2,2)$，拿走结点 $2$ 上面的苹果，在纸上写下 $1,2,2$。 最终形成了 $a=(3,4,3,1,2,2)$，可以证明这是字典序最大的合法结果。 By chenxi2009