题目内容

塔子哥是一个热爱冒险和探索的年轻人。有一天，他看到了一张神秘的照片，照片上有一颗挂着红薯的树。这个景象让塔子哥觉得非常有趣，他决定也要种一颗树，并挂上一些红薯，以此分享他的冒险故事。

塔子哥收集了一颗神奇的数树种子，这颗数树与普通树不同，每个结点都有一个特殊的权值。初始时，所有节点都是白色的。塔子哥发现每次可以选择两个相邻的白色节点，并且它们的权值之和必须是质数。一旦满足这个条件，塔子哥就可以选择其中一个节点染成红色。

现在，塔子哥想知道，在这颗数树上，最多可以染红多少个节点。

输入描述

第一行输入一个正整数$n$，代表节点的数量

第二行输入$n$个正整数$a_i$，代表每个节点的权值

接下来的n-1行每行输入两个正整教$u,v$，代表节点$u$和节点$v$有一条边连接

$1 \leq n \leq 10^5$

$1 \leq a_i \leq 10^5$

$1 \leq u,v \leq n$

输出描述

输出一个整数表示正确答案。

4
1 2 3 4
1 2
2 3
3 4

3