Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Gujob

By ghazanfar · Limits 1s, 512 MB

You probably heard the name of ‘Kababdesh’, where people are very fond of kababs. Everyone live there with peace and harmony. But recently they came to know that many people of their country is affected by a disease called Accepting Gujob Disorder (AGD). This happened because suddenly many people lacking Gujob Resistance Power (GRP) in their blood. As a result, everything became a mess. To solve this issue and understand how many people might get affected to it the Government of Kababdesh wants your help.

You know the follwing things:

  1. Everyone of Kababdesh has a GRP.
  2. Anyone with a GRP of 0 instantly got affected by AGD.
  3. If anyone got affected by AGD, instantly his friends lost GRP by 1.

You are given the GRP of everyone in Kababdesh and also who is friend of whom. Can you help with how many people will get affected ?

Input

The first line contains two numbers, N (1 ≤ N ≤ 103) and M (0 ≤ M ≤ 103). Where N denote the total number of people in Kababdesh and M denotes the number of friendship. In the next line, there are N integers where Ni denotes GRP (0 ≤ GRPi ≤ N) of the i-th person. Then there are M lines. Each line contains two integer a and b (1 ≤ a, b ≤ N) denoting a is a friend of b and vice versa.

Output

Print a single integer, the number of people to be affected by AGD.

Samples

InputOutput
3 3
0 1 2
1 2
2 3
3 1
3
InputOutput
3 3
1 2 3
1 2
2 3
3 1
0


Discussion
Submit

Login to submit