The coronavirus pandemic has hit the country of Stablanija hard. The country consists of $N$ cities connected by $N-1$ edges, forming a tree.

The almighty pandemic response headquarters has divided the country into $K$ counties for the purpose of introducing travel permits. The only thing left to do is to select county centers that will be responsible for epidemiological measures and county informatics competitions.

The rules are very strict: if a city $v$ is located in county $i$ ($1 \le i \le K$), then $v$ must be strictly closer to the center $c_i$ of that county than to the center of any other county. Formally, $d(v, c_i) < d(v, c_j)$ for all $j \neq i$, where $d(x, y)$ denotes the distance along the tree edges between cities $x$ and $y$.

Is it possible to select the county centers in the required manner?

Input

The first line contains the natural numbers $N$ and $K$ from the problem description.

The second line contains $N$ natural numbers $a_i$ ($1 \le a_i \le K$), the county labels of the cities. Each county will contain at least one city.

In each of the next $N-1$ lines, there are two distinct natural numbers $u_j, v_j$ ($1 \le u_j, v_j \le N$), representing the cities connected by the $j$-th edge of the tree.

Output

In the first line, print DA or NE, the answer to the question from the problem.

If the answer is DA, in the second line print $K$ numbers $c_1, \dots, c_K$, such that city $c_i$ is the center of county $i$.

Subtasks

If you correctly printed the first line in all test cases of a subtask, but printed an incorrect construction in the second line for some test case, you will receive 40% of the points for that subtask.

Examples

Input 1

3 2
1 1 2
1 2
2 3

Output 1

DA
2 3

Input 2

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

Output 2

NE

Input 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

Output 3

DA
1 2 8

Note

Explanation of the third example: