题目背景

译自 Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection) D1T3。$\texttt{2s,0.5G}$。

题目描述

给定 $N$ 个点的树。已经将这 $N$ 个点划分成了 $K$ 个县。

现在你要为每个县确定一个县城。设第 $i$ 个点属于的县为 $B_i$，每个县的县城为 $A_1,A_2,\cdots,A_K$（必须两两不同），则下列关系式必须满足：

• $\forall 1\le i\le N$，$\displaystyle \operatorname{dist}(i,A_{B_i})\lt \min_{j=1,j\neq B_i}^K \operatorname{dist}(i,A_j)$。

其中，$\mathrm{dist}(a,b)$ 定义为 $a,b$ 之间简单路径的边数。

也就是说，每个县中的点到它所属的县城距离必须严格小于到其它县城的距离。

判断这是否是可以达成的。如果可以的话，需要给出一组符合条件的方案。

输入格式

第一行，两个正整数 $N,K$。

第二行，$N$ 个整数 $B_1,B_2,\cdots,B_N$。

接下来 $(N-1)$ 行，每行两个正整数 $u,v$，描述一条树边 $(u,v)$。

输出格式

如果可行的话，第一行输出 DA（克罗地亚语「是」）；第二行 $K$ 个整数，第 $i$ 个整数表示第 $i$ 个县的县城。

否则输出 NE（克罗地亚语「否」）。

3 2
1 1 2
1 2
2 3

DA
2 3

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

NE

8 3
1 2 1 2 2 1 3 3
1 2
1 3
2 4
2 5
3 6
3 7
7 8

DA
1 2 8

提示

样例解释

下图是样例 $3$ 的解释。

数据范围

【评分方式】如果你回答对了第一问，可以获得 $40\%$ 的分数。但是需要保证输出格式正确，即，如果只打算回答第一问，也要在第二行输出 $K$ 个不同的 $\in [1,N]$ 的整数。

对于 $100\%$ 的数据，保证 $1\le B_i\le K\le N\le 2\times 10^5$，给出的是一棵树。

子任务编号	$N\le$	特殊性质	得分
$1$	$20$	无	$10$
$2$	$2\, 000$		$25$
$3$	$2\times 10^5$	有	$30$
$4$		无	$35$

特殊性质：每个点的度数为 $1$ 或 $3$。