#B. 简单构造

Type: RemoteJudge

1000ms

256MiB

题目描述

给定 $n$ 个点的以 $1$ 为根的树，构造字典序最小排列 $p$ 使对于 $\forall1\le i,x<i+x\le n$ ，有 $d_{p_i}-d_{p_{i+x}}\equiv x\pmod 2$ ，其中 $d_i$ 表示 $i$ 节点在树上的深度。

第一行，一个整数 $t$ 表示测试数据组数。对于每一个测试数据：第一行，一个正整数 $n$ 。接下来 $n-1$ 行，每行两个正整数 $u,v$ 表示一条树边。

对于每一组测试数据： $n$ 个数，表示排列 $p$ ，要求字典序最小！（无解请只输出 -1）。

1 2 3
-1

对于所有数据，都有 $1\le t,n,\sum n\le 10^5$ ，保证有 $1 \leq u, v \leq n$ 且 $u \neq v$ 。保证输入构成一棵树。其中 $\sum n$ 表示所有测试数据的 $n$ 的总和。