题目描述

在一个古老的村庄中，有一种神秘的涂色仪式。这个村庄有一个复杂的树状结构，每个节点都有一个特定的权值。在仪式开始时，所有的节点都是黑色的。

但是，村民们发现了一些奇特的规则，只要相邻的两个结点满足以下两个条件：

• 颜色都是黑色；
• 权值之和是质数。

村民们就可以选择其中一个节点变成白色。你的任务是确定在这些条件下，最多可以有多少节点变成白色。

输入格式

第一行包含一个整数 $𝑛$，表示节点的数量，$n\le 3\times 10^5$。

第二行包含 $𝑛$ 个整数 $a_i$，表示每个节点的权值，$a_i\le 10^6$。

接下来的 $𝑛−1$ 行，每行输入两个正整数 $𝑢$ 和 $𝑣$，表示节点 $𝑢$ 和节点 $𝑣$ 之间有一条边连接。

输出格式

输出一个整数，表示最多可以有多少节点变成白色。

3
1 2 3
1 2
1 3

1

数据范围/提示

样例 $2$ 见附加文件。