← 返回题目列表

Codeforces · 498/C

C. 数组和运算

中文机器翻译题面 查看原题

你在一张纸上写下了一个由 n 个正整数 a[1], a[2], ..., a[n] 和 m 个好整数对 (i1, j1), (i2, j2), ..., (im, jm) 组成的数组。每个好对 (ik, jk) 满足以下条件:ik + jk 是奇数且 1 ≤ ik < jk ≤ n。

在一个操作中,您可以执行一系列操作:

- 取一个好的对 (ik, jk) 和一些整数 v (v > 1),它可以除以 a[ik] 和 a[jk];
- 将两个数字除以 v, i。 e.执行赋值:$$a[i_k] = \frac{a[i_k]}{v}$$ 和 $$a[j_k] = \frac{a[j_k]}{v}$$。

确定可以对给定数组连续执行的最大操作数。请注意,一对可以在所描述的操作中使用多次。

输入

第一行包含两个空格分隔的整数 n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100)。

第二行包含 n 个空格分隔的整数 a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — 数组的描述。

接下来的 m 行包含了好对的描述。第 k 行包含两个空格分隔的整数 ik、jk(1 ≤ ik < jk ≤ n,ik + jk 为奇数)。

保证所有好的配对都是不同的。

输出

输出问题的答案。

示例

输入 #1

3 2
8 3 8
1 2
2 3

输出 #1

0

输入 #2

3 2
8 12 8
1 2
2 3

输出 #2

2