简单题(perm)

题目描述

zzh 有一棵 $n$ 个点的树，在这棵树上有一个棋子，这个棋子初始在点 $1$ 。棋子只能沿着树边移动。

cjz 有一个 $n-1$ 阶排列 $p$ 。某一天夜晚，cjz 来到了 zzh 的树前。他依次执行了 $n$ 步操作：

在前 $n-1$ 步操作中，第 $i$ 步他将棋子从当前位置沿着最短路径移动到了点 $p_i+1$。

在最后一步操作中，他将棋子从当前位置沿着最短路径移动到了点 $1$。

第二天早上，zzh 发现了 cjz 的操作。她得出了这个棋子在 cjz 操作的过程中经过的边的条数 $k$ ，但她不知道 cjz 的排列。zzh 把这个问题交给了你。因此你需要求出任意一个满足按照这个排列操作，操作的过程中经过的边的条数为 $k$ 的排列。如果不存在这样的排列，你需要告诉 zzh 她求出了错误的 k。

然而，cjz 连续 $T$ 天在夜晚进行了这样的操作。因此你需要在每一天早上回答 zzh 的问题。同时，神仙的树每天都会发生变化，因此每天的树都会改变，但每天 cjz 操作前棋子都在位置 $1$。

即在 $T$ 天中的每一天，给出 $n$，一棵 $n$ 个点的树以及 $k$ ，你需要求出任意一个 $n-1$ 阶排列 $p$ 满足如下条件或报告无解：

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

这里 $dis(i,j)$ 为两点在树上的最短路径经过的边数， 认为 $p_0=p_n=0$。

输入格式

从文件 perm.in 读入。

输入第一行包含一个整数 $T$ ，表示询问的天数。接下来若干行依次表示每一天的情况：

对于每一天：

首先一行包含两个正整数 $n,k$ ，含义见题面。

然后 $n-1$ 行，每行两个正整数 $a_i,b_i$ ，表示这棵树的所有边。

输出格式

输出到文件 perm.out。

输出 $T$ 行，每一天输出一行，按照输入的顺序输出每一天：

如果这一天的询问不存在合法的排列，则这一行输出一个数 $-1$。

否则这一行输出 $n-1$ 个以单个空格分隔的正整数 $p_{1,...,n-1}$ ，表示你求出的排列。

本题使用SPJ，但你可以输出额外的行末空格和文末回车。

样例

样例输入1

2
5 10
1 2
2 3
3 4
3 5
5 12
1 2
2 3
3 4
3 5

样例输出1

4 2 1 3
-1

样例解释1

对于第一组数据：

$dis(1,5)=3,dis(5,3)=1,dis(3,2)=1,dis(2,4)=2,dis(4,1)=3$

因此它们的和为 $10$，满足条件。

对于第二组数据，经过验证不存在满足条件的排列。

样例输入/输出 2~5

见下发文件

样例 $1\sim 5$ 依次满足测试点 $2,4,6,8,10$ 的限制。

需要注意的是，下发文件中的 .ans 文件中的输出只代表所有解中的一组解。但你可以输出任意一组满足要求的解。

数据范围与限制

对于所有数据，保证 $3\leq n\leq 10^6,\sum n\leq 2\times 10^6,k\leq 10^{12}$，输入的边构成一棵树。

测试点编号	特殊限制
$1$	$T=0$
$2,3$	$n\leq 9,T\leq 5$
$4,5$	$n\leq 13,T\leq 5$
$6,7$	$\sum n\leq 2000$，第 $i$ 条树边连接 $(i,i+1)$
$8,9$	$\sum n\leq 2000$，任意两点间路径经过的边数不超过 $3$
$10,11$	$\sum n\leq 2000$
$12,13$	$\sum n\leq 2\times 10^5$，第 $i$ 条树边连接 $(i,i+1)$
$14,15$	$\sum n\leq 2\times 10^5$，任意两点间路径经过的边数不超过 $3$
$16,17,18$	$\sum n\leq 2\times 10^5$
$19,20$	无特殊限制

友情提示：读入不规范，爆零两行泪。

本题需要输入/输出优化