사탕 균등 분배

엔드레에게는 조카가 많다. 일 년에 한 번, 그는 조카 몇 명을 데리고 군도로 여행을 간다. 그곳에서는 선박 회사 한 곳이 일부 섬 쌍 사이에 양방향 배편을 운영한다. 엔드레 일행은 어느 섬으로든 비행기로 곧장 들어가고 나올 수 있으므로, 여행 하나는 비어 있지 않은 섬 수열 $i_1, i_2, \dots, i_n$으로 나타낼 수 있다. 수열에서 이웃한 두 섬 $i_j$와 $i_{j+1}$ 사이에는 배편이 있어야 한다. 첫 섬과 마지막 섬은 같아도 되고 달라도 된다. 같은 섬을 여러 번 방문해도 된다.

섬마다 만드는 사탕이 다르고, 도착한 일행에게 정해진 개수만큼 사탕을 준다. 엔드레는 사탕을 좋아하지 않지만 아이들은 받자마자 다 먹어 치운다. 다툼을 막으려고 그는 일행이 섬에 도착해 사탕을 받을 때마다 아이들에게 똑같이 나눠 준다. 아이가 $k$명이면 여행에서 방문한 모든 섬의 사탕 개수가 $k$로 나누어떨어져야 한다는 뜻이다.

엔드레가 해마다 사탕을 똑같이 나눌 수 있는 이유는 간단하다. 여행사가 여행 계획, 즉 수열 $i_1, i_2, \dots, i_n$을 미리 보내 준다. 그는 조카를 되도록 많이 데려가고 싶으므로, 똑같이 나눈다는 규칙을 어기지 않는 한도에서 데려갈 아이 수의 최댓값 $k$를 구한다. 아이는 한 명 이상 데려간다. 여행 계획 하나가 데려갈 아이 수를 하나로 정한다.

여행이 여러 해 이어지는 동안 데려간 아이 수는 매번 달랐다. 엔드레는 데려갈 수 있는 아이 수가 몇 가지인지 궁금하다. 어떤 여행 계획을 세우면 아이를 정확히 $k$명 데려가게 되는, 그런 정수 $k$가 몇 개인지 구하라.

첫 줄에 섬의 수 $I$와 배편의 수 $S$가 주어진다 ($1 \le I, S \le 10^4$). 섬은 $1$부터 $I$까지 서로 다른 정수로 구분한다.

둘째 줄에 정수 $C_1, C_2, \dots, C_I$가 주어진다. $C_i$는 섬 $i$에 도착한 일행이 받는 사탕 개수다 ($1 \le C_i \le 10^5$).

다음 $S$개 줄에는 각각 배편 하나를 나타내는 두 정수 $A$와 $B$가 주어진다 ($1 \le A < B \le I$). 섬 $A$에서 섬 $B$로, 섬 $B$에서 섬 $A$로 갈 수 있다는 뜻이다. 같은 섬 쌍을 잇는 배편이 두 번 이상 주어지지는 않는다.

어떤 여행 계획으로 아이를 정확히 $k$명 데려가게 되는 정수 $k$의 개수를 한 줄에 출력한다.