本来这里应该有一份符合出题人 $2022$ 年时写题面的风格（大概来说就是很长）的题目背景，但出题人某天晚上交作业的时候被酒店阴间的Wifi质量恶心到了，同时出题人的笔记本坏了，因此他并没能在ddl前写出这样的背景。

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

小 Z 想要找到一个 排列 或者 环排列，使得从排列的第一个点出发按照排列的顺序访问所有点后，总共经过的边数正好是 $k$。

具体来说，给定 $op\in\{1,2\}$，你需要找到一个 $n$ 阶排列 $p$，满足如下条件：

1. 如果 $op=1$，你需要满足 $\sum_{i=1}^{n-1}dis(p_i,p_{i+1})=k$。
2. 如果 $op=2$，你需要满足 $\sum_{i=1}^ndis(p_i,p_{(i\ \bmod\ n)+1})=k$。

这里 $dis(x,y)$ 为树上 $x,y$ 节点间最短路径经过的边数。

小 Z 完全不会 OI，因此他希望你能找到一组解，或者告诉他不存在这样的解。如果有多个可能的解，你可以输出任意一个满足条件的解。

小 Z 有 $T$ 个这样的问题，你需要回答小 Z 的每一个问题。

输入格式

输入文件第一行包含一个非负整数 $T$，表示数据组数，接下来依次给出每组数据。

对于一组数据，第一行包含三个正整数 $n,k,op$，表示树的点数以及小 A 要求的总路程，还有小 A 的询问类型。

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

输出格式

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

如果这组数据中不存在满足要求的排列，则输出一个数 $-1$。

否则，在这一行中输出 $n$ 个整数 $p_1,\cdots,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

对于第一组数据，可以发现 $dis(3,4)=3,dis(4,2)=1,dis(2,1)=1,dis(1,5)=2$，因此它满足小 Z 对于排列的要求。

对于第二组数据，可以证明不存在解。

对于第三组数据，显然唯一的一种方案满足条件。

样例输入 #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

这组样例的情况与上一组类似，唯一的区别在于 $op=2$，因此此时计算距离时需要额外计算 $dis(p_1,p_n)$。

数据范围与限制

对于所有数据，保证 $T\leq 5\times 10^5,1\leq n\leq 5\times 10^5,\sum n\leq 5\times 10^5,0\leq k\leq n^2,op\in\{1,2\},1\leq u_i,v_i\leq n$，给出的边构成一棵合法的树。

在一个子任务中，如果你正确地回答了所有 $op=1$ 的询问或者所有 $op=2$ 的询问，但没有正确回答所有询问，则你可以获得 $50\%$ 的分数。

注意：如果你只想获得 $op=1$ 或 $op=2$ 部分的分数，你也需要在剩余数据上输出符合格式的内容。任意一组数据上输出格式错误将 可能导致整个子任务获得 $0$ 分。