题目描述

给定一棵有 $n$ 个节点的树，第 $i$ 条边连接 $u_i,v_i$。

需要找到一个 $n$ 阶排列 $p$，使得按照排列顺序访问所有节点时，总经过边数恰好为 $k$。根据参数 $op\in\{1,2\}$，有两种要求：

1. 若 $op=1$，要求

   $$\sum_{i=1}^{n-1} dis(p_i,p_{i+1})=k.$$

2. 若 $op=2$，要求

   $$\sum_{i=1}^{n} dis(p_i,p_{(i\bmod n)+1})=k.$$

其中 $dis(x,y)$ 表示树上 $x,y$ 之间最短路径经过的边数。

若存在多个方案，输出任意一个；若不存在，输出 -1。

输入格式

第一行输入一个非负整数 $T$，表示数据组数。

接下来依次给出每组数据。每组数据第一行包含三个整数 $n,k,op$。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$，表示一条树边。

输出格式

对于每组数据，输出一行。

若无解，输出一个整数 -1。

否则输出 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示一个满足条件的排列。

样例

样例输入 1

3
5 7 1
1 2
1 3
2 4
2 5
4 6 1
1 2
1 3
1 4
1 0 1

样例输出 1

3 4 2 1 5
-1
1

样例输入 2

3
5 10 2
1 2
1 3
2 4
2 5
4 6 2
1 2
1 3
1 4
1 0 2

样例输出 2

3 4 2 1 5
1 2 3 4
1

数据范围与限制

对所有数据：

• $T\le 5\times 10^5$；
• $1\le n\le 5\times 10^5$；
• $\sum n\le 5\times 10^5$；
• $0\le k\le n^2$；
• $op\in\{1,2\}$；
• 输入边构成一棵合法的树。

若只正确回答所有 $op=1$ 或所有 $op=2$ 的询问，可以获得 $50\%$ 分数；但其它询问也必须输出合法格式。