10399번 - Even distribution 다국어

Endre has lots of nieces and nephews. Once a year, he takes some of them on a trip to an archipelago where a boat company operates two-way services between some pairs of islands. Since Endre and the children can fly and return directly to or from any of the islands, any trip can be described as a nonempty sequence i₁, i₂, . . . , i_n of islands, such that each pair of consecutive islands i_j and i_j+1 have a boat service between them. The first and the last islands of a trip may or may not be the same island, and the islands may be visited more than once during the trip.

Each island in the archipelago produces a different peculiar variety of candy, and greets its visitors by giving each arriving group a fixed number of pieces of candy. Endre does not like candies himself, but the children eat them all almost instantly. To avoid fights, each time the group arrives to an island and receives candies, he evenly distributes them among the children.

You may wonder how Endre always manages to evenly distribute the candies they receive in each island. Well, the answer is actually very simple. Each year, the travel agency sends him the trip plan (the sequence i₁, i₂, . . . , i_n) beforehand. Since he wants to travel with as many of his nieces and nephews as possible, he calculates the maximum number k of kids he can take on the trip without violating the rule about the even distribution of candy. Notice that each trip plan uniquely determines the number of kids to take.

This has been going on for years, and each time Endre ends up taking a different number of kids on the trip. He would like to know how many different numbers of kids he can take on a trip, that is, the number of integers k such that there is a trip plan for which he ends up taking k kids on the trip. Right now Endre is very busy preparing this year’s trip. Can you help him with the answer?

The first line contains two integers I and S (1 ≤ I, S ≤ 10⁴), representing respectively the number of islands and the number of boat services between them. Islands are identified with distinct integers from 1 to I. The second line contains I integers C₁, C₂, . . . , CI , where Ci indicates the number of pieces of candy the group receives when arriving at island i (1 ≤ C_i ≤ 10⁵ for i = 1, 2, . . . , I). Each of the next S lines describes a different boat service with two integers A and B (1 ≤ A < B ≤ I), representing that it is possible to travel from island A to island B and from island B to island A. No two boat services allow to travel between the same pair of islands.

Output a line with an integer representing the number of integers k such that there is a trip plan for which Endre ends up taking k kids on the trip.