RoAlgo Contest #9 | City Skylines

Task

JellyTheOctopus has just gotten the game City Skylines! The goal of the game is to create a prospering city. So far, Jelly's city has $N$ districts (named from $1$ to $N$) connected by $M$ different connection roads (two districts have at most one undirected road traveling between them).

There are three types of districts: industry, business, and living. An industry district is where the city gets its resources (e.g. from mining, logging, farming, etc.). No one wants to deal with coal mines, so every industry district contributes $-1$ points to the total prosperity of Jelly's city. A business district is where all the companies and jobs of the city are located. As this is the money-making part of the city, each business district contributes $1$ point to the total prosperity of Jelly's city. A living district is where all the houses and apartments are located. These are just a basic necessity, so each living district contributes $0$ points to the total prosperity of the city.

Not only does Jelly care about the overall prosperity of his city, he also wants his city to be balanced. The definition of a balanced city is as follows: for every district $a_i$, the prosperity of district $a_i$ must be equal to the sum of the prosperity of all adjacent districts (meaning all districts connected to $a_i$ by a single road). The current state of Jelly's city may not be balanced. For this reason, he asks you to help him make his city balanced. You can add new districts as follows: take any district already in Jelly's city, then connect a completely new district (of any type) with a road. Once you add a new district, it becomes a part of Jelly's city (so you could add another new district to the one you just created). Also, you must add a single city at a time.

Help Jelly find the minimum number of new districts needed to create a balanced city.

Input data

On the first line there are two integers, $N$ and $M$, representing the number of districts, and the number of roads connecting two districts together.

The next line consists of $N$ integers, $a_i$, representing the type of each district (either a $-1$, $0$, or $1$).

The next $M$ lines consists of two integers, $u$ and $v$, representing an undirected road between districts $u$ and $v$.

Output data

Output a single integer $K$, the minimum number of districts needed for Jelly to have a balanced city.

Constraints and clarifications

• $1 \leq N \leq 10^5$;
• $1 \leq M \leq \min(10^5, \frac{N \cdot (N-1)}{2})$;
• $-1 \leq a_i \leq 1$;
• Each pair of districts have at most one road connecting them.
• By the nature of adding new districts, if there are $K$ new districts, there should be exactly $K$ new roads between districts.

Example

stdin

3 2
0 1 -1
1 2
1 3

stdout

2

Explanation

Further clarification about adding new districts: If, for example, Jelly has a city of $5$ districts, you could add a new district to district $5$. (Thus, there is now a road between district $5$ and district $6$, and Jelly's city is now consisted of $6$ districts). District $6$ is now a part of Jelly's city, and you cannot create a road from district $6$ to districts $1$ through $5$. However, because district $6$ is now a part of the city, you can now add a new city to district $6$ (e.g. a new road between district $6$ and district $7$).