题目描述

春雪异变之后，小庭师 youmu 对西行妖起了兴趣

youmu 发现，西行妖可以抽象为一棵具有 $n$ 个结点，并以 $1$ 号点为根的完全二叉树

（在本题中，我们定义 “完全二叉树” 是指除了叶子结点之外每个结点都恰有两个儿子的二叉树）

西行妖的每个结点上都有一朵樱花，第 $i$ 号结点上的樱花颜色为 $a_i$。对于大部分结点来说，它们的花朵颜色即结点编号，即 $a_i=i$，但是由于春度的作用，有 $k$ 个结点上的花发生变异使 $a_i\ne i$ ，但它们的 $a_i$ 仍在 $[1,n]$ 间

作为庭师，youmu 现在可以任意调整西行妖的形态，具体来说：

• 每次调整，youmu 可以交换这棵二叉树上一个结点的左右儿子

youmu 认为，只有西行妖进行中序遍历所得的颜色序列字典序最小时，它才是最美的

由于 youmu 呆呆的，请你帮她求出这个最小的颜色序列

（如果你不知道什么是 “字典序”，请见题面最后的补充说明部分）

输入格式

本题采用多组数据测试

输入数据第一行为 $T$，表示数据的组数

接下来 $T$ 组数据，每组结构如下：

一组数据共 $n+1$ 行

第一行两个整数 $n$，$k$

第二行 $n$ 个整数表示 $a_1,\ a_2,\ \dots,\ a_n$

接下来 $n-1$ 行，每行两个整数 $u,v$，表示二叉树上存在一条连接 $u$ 号结点和 $v$ 号结点的边

输出格式

共 $T$ 行，对于每组数据输出一行共 $n$ 个整数，表示可能的最小中序遍历序列

样例数据

样例一

输入

1
5 4
4 1 1 1 5
1 2
1 3
2 4
2 5

输出

1 1 5 4 1

此样例与下发文件 youmu_ex1.in/youmu_ex1.out 相同

样例二

输入

1
15 5
1 2 10 4 5 3 5 8 9 10 11 12 13 6 8
11 2
1 3
8 14
14 13
11 5
3 6
1 11
5 10
10 7
8 9
10 12
3 8
5 4
14 15

输出

2 11 4 5 5 10 12 1 3 10 8 6 13 8 9

此样例与下发文件 youmu_ex2.in/youmu_ex2.out 相同

样例三

见下发文件 youmu_ex3.in/youmu_ex3.out

下发文件

点击下载

数据范围与约定

对于全部数据：保证所给的边能连接成为一棵完全二叉树，

$1\le T\le 3$，$1\le n\le 3\times 10^5$，$0\le k\le \min(2000, n)$，$1\le a_i\le n$

部分分	分数占比	测试点数量	$n$	$k$	特殊性质
$1$	$16\%$	$8$	$1\le n \le 10$	$0\le k\le n$	无
$2$	$14\%$	$7$	$1\le n\le 1000$	$0\le k \le 10$
$3$	$30\%$	$6$	$1\le n\le 3\times 10^5$	$k=0$
$4$	$10\%$	$5$		$0\le k\le 2000$	非叶子结点的子树中总存在一点使得 $a_i = i$
$5$	$30\%$	$6$			无

补充说明

字典序

设有序列 $s,\ t$，不妨令 $s$ 长度不超过 $t$

若 $s=t$，则字典序上也有 $s=t$；否则若 $s$ 是 $t$ 的一个前缀，则称字典序 $s<t$；否则从前往后依次比对，找到 $s$ 与 $t$ 第一个不同的位置 $p$，若 $s_p<t_p$，称字典序 $s<t$，否则必有 $s_p>t_p$，称字典序 $s > t$