Description

Original source: CQOI 2009

Given an unrooted tree with $m$ nodes, you can select a node with a degree greater than $1$ as the root. Then, color some nodes (the root, internal nodes, or leaves) either black or white. Your coloring scheme must ensure that every simple path from the root to any leaf node contains at least one colored node, even if it's the leaf itself.

For each leaf node $u$, define $c_u$ as the color of the last colored node on the simple path from the root to $u$. Given the value of each $c_u$, design a coloring scheme that minimizes the number of colored nodes.

Input Format

The first line contains two integers $m$ and $n$, representing the total number of nodes and the number of leaves, respectively. The nodes are numbered from $1$ to $m$.

The next $n$ lines each contain a value of $0$ or $1$, where $0$ represents black and $1$ represents white, corresponding to the values of $c_1, c_2, \cdots, c_n$ in order.

The following $m-1$ lines each contain two integers $a$ and $b$, indicating that there is an edge between nodes $a$ and $b$.

Output Format

Output a single integer, representing the minimum number of colored nodes.

Sample 1

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

2

Data Range and Hints