题目描述

小明是一位尽职尽责的园丁。这天他负责维护一棵树，树上有 $n$ 个结点 $1, 2, \ldots, n$，根结点为 $1$，结点 $i$ 的权值为 $a_i$。他需要更改一些结点的权值为任意正整数，使得对于任意一个至少有 $2$ 个儿子结点的结点 $i$ 满足：任意两个 $i$ 的儿子结点的权值的乘积都不是完全平方数。请问小明至少需要修改多少个结点的权值？

输入格式

输入共 $n+1$ 行。

第一行为一个正整数 $n$。

第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \ldots, a_n$。

后面 $n-1$ 行，每行两个正整数表示树上的一条边。

输出格式

输出共 $1$ 行，一个整数表示答案。

6
1 2 9 8 4 4
1 2
1 3
1 4
2 5
2 6

2

提示

样例说明

其中一种方案：将结点 $2, 5$ 的权值分别修改为 $3, 2$。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，保证 $n \leq 10^3$。
• 对于 $100\%$ 的评测用例，保证 $1\leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。