小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。 小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。 小美想知道，自己最多可以染红多少个节点？

输入描述:

第一行输入一个正整数，代表节点的数量。第二行输入个正整数，代表每个节点的权值。接下来的行，每行输入两个正整数，代表节点和节点有一条边连接。

输出描述:

输出一个整数，表示最多可以染红的节点数量。