新冠疫情严重影响了 Stablanija 国。该国由 $N$ 个城市组成，这些城市通过 $N-1$ 条边连接，构成一棵树。

全能防疫指挥部为了实施通行证制度，将该国划分为 $K$ 个县。现在唯一剩下的任务是选出各县的中心，负责防疫措施和县级信息学竞赛。

规则非常严格：如果城市 $v$ 位于县 $i$ ($1 \le i \le K$) 中，则 $v$ 必须严格更靠近该县的中心 $c_i$，而不是任何其他县的中心。形式化地，对于所有 $j \neq i$，满足 $d(v, c_i) < d(v, c_j)$，其中 $d(x, y)$ 表示树上城市 $x$ 和 $y$ 之间的边距离。

请问是否可以按要求选出县中心？

输入格式

第一行包含题目描述中的自然数 $N$ 和 $K$。

第二行包含 $N$ 个自然数 $a_i$ ($1 \le a_i \le K$)，表示各城市所属的县。每个县至少包含一个城市。

接下来的 $N-1$ 行中，第 $j$ 行包含两个不同的自然数 $u_j, v_j$ ($1 \le u_j, v_j \le N$)，表示树的第 $j$ 条边连接的两个城市。

输出格式

第一行输出 DA 或 NE，作为对题目问题的回答。

如果回答为 DA，则在第二行输出 $K$ 个整数 $c_1, \dots, c_K$，使得城市 $c_i$ 为县 $i$ 的中心。

子任务

如果您在某个子任务的所有样例中正确输出了第一行，但在某个样例中第二行输出了错误的构造，您将获得该子任务 40% 的分数。

样例

输入 1

3 2
1 1 2
1 2
2 3

输出 1

DA
2 3

输入 2

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

输出 2

NE

输入 3

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

输出 3

DA
1 2 8

说明

第三个样例的解释：