题目内容

小塔有一棵$n$个节点的树，$1$号节点是树的根节点。$i$号节点的权值为$a_i$，如果边($u,v$)的两个端点权值的质因子个数相同，那么这条边需要被染色。例如，$6$有两个质因子，分别是$2$和$3，4$只有一个质因子$2$。 小塔每次可以选择一个点，将这个点到根节点的所有边染色，请问最少需要操作多少次，才能使得所有需要被染色的边都被染色。

输入描述

第一行输入一个整数$n$($2≤n<10^5$)，表示树的节点数。 第二行输入$n$个整数$a_1,a_2,...,a_n$($1≤a_i≤10^7$)，表示每个节点的权值。 此后$n-1$行,第$i$行输入两个整数$u_i$和$v_i$($1≤u_i,vi≤n; u_i≠v_i$)表示树上第$i$条边连接节点$u_i$和$v_i$。保证树联通，没有重边。

输出描述

先输出一个整数，表示最少需要操作的次数。 如果需要的操作次数不为零，接下来一行，从小到大输出若干整数，表示每次操作选择的点。

样例1

输入

6
2 2 3 4 30 6
1 2
2 3
2 4
1 5
5 6

输出

2
3 4

说明

$6$个点的权值质因子个数分别为[$1,1,1,1,3,2$]，所以需要染色的边为($1,2$),($2,3$),($2,4$)，最少需要操作$2$次，先选择$3$号点，再选择$4$号点。