| Codeforces Round 284 (Div. 1) |
|---|
| Закончено |
Вы выписали на листок массив из 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, т. е. выполнить присваивания:
и 
.
Определите, какое максимальное количество операций можно последовательно совершить над данным массивом. Обратите внимание, что одну пару можно использовать несколько раз в описанных операциях.
В первой строке записано два целых числа через пробел 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 — нечетное число).
Гарантируется, что все хорошие пары различны.
Выведите единственное целое число — ответ на задачу.
3 2
8 3 8
1 2
2 3
0
3 2
8 12 8
1 2
2 3
2
