测试数据来自 system/1550

描述

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。

对于每个叶结点u，定义c[u]为从u到根结点的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

格式

输入格式

第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。

以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。

以下m-1行每行两个整数a，b（1<=a < b <= m），表示结点a和b 有边相连。

输出格式

仅一个数，即着色结点数的最小值。

样例1

样例输入1

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

样例输出1

2

限制

后三个测试点限时2s，其余1s。

提示

对于50%的数据，m<=400，n<=197；
对于70%的数据，m<=4000，n<=2044；
对于全部的数据，m<=10000，n<=4996；
管理员提示:由于数据的问题,请用Read读入数据

来源

NOI2009重庆市代表队选拔赛第二题