Music Fest

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type

Ms. Holland has been pestering her N students for their permission forms for MusicFest for a while now. Every rehearsal, she reminds the students, but it seems either nobody has been paying attention, or nobody cares enough to actually fill it out. Ms. Holland has had enough.

After some digging, Ms. Holland discovers that Q of the students only attend morning band rehearsals because their friends are there. Of these Q students, she also learns that the a_i-th student will only fill out the permission form if the b_i-th student (whom the student looks up to) has filled out the form. With this information in hand, Ms. Holland realizes she only needs to pester a few of the students to fill out the form, and others will follow suit.

Ms. Holland wonders what the minimum number of students she must pester is, such that in the end, the entire band has filled the form.


1 \le N, Q \le 10^5

1\le a_i,b_i\le N

a_i\ne b_i

Each a_i is distinct

Input Specification

The first line will contain integers N and Q.

The next line will contain N space-separated integers, either 0s or 1s, indicating if the i^{th} student has signed their permission form or not. 1 indicates that they have, and 0 indicates they have not.

The next Q lines will contain two integers, a_i and b_i, indicating that student a_i looks up to student b_i.

Note: The input is not propagated - i.e. there is a possibility that b_i will have a value of 1 while a_i has a value of 0. Student a_i will still sign the form even though it is not initially specified.

Output Specification

Output one integer, the minimum number of students Ms. Holland must pester.

Sample Input

15 12
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
1 2
2 3
3 4
4 2
5 1
6 1
7 6
8 9
9 10
10 11
12 13
14 15

Sample Output


Sample Explanation

If Ms. Holland pesters student 4, 11, and 15, all of the other students will eventually fill out their permission forms.


There are no comments at the moment.