Practice on Toph

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


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 ?


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.


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


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



100% Solution Ratio

touhidurEarliest, 11M ago

touhidurFastest, 0.0s

touhidurLightest, 131 kB

touhidurShortest, 182B


Login to submit