Koprocessor
Sizə bir sıra tapşırıqlardan ibarət proqram təqdim olunub. Bu tapşırıqlar istiqamətli asiklik asılılıq qrafında təşkil edilib: hər bir tapşırıq bir və ya bir neçə digər tapşırığın icra nəticələrindən asılı ola bilər və qrafda tapşırıqlar arasında istiqamətli dövri asılılıqlar yoxdur. Hər bir tapşırıq yalnız ondan asılı olan bütün tapşırıqlar icra edildikdən sonra icra edilə bilər.
Qrafda bəzi tapşırıqlar köməkçi prosessorda, digərləri isə əsas prosessorda icra olunmalıdır. Köməkçi prosessoru bir dəfə çağırmaqla ona icra olunmalı tapşırıqların siyahısını ötürə bilərsiniz. Siyahıdakı hər bir tapşırıq üçün, ondan asılı olan bütün tapşırıqlar ya artıq icra olunmuş, ya da həmin siyahıda olmalıdır. Əsas prosessor proqramın icrasına başlayır və avtomatik olaraq köməkçi prosessordan tapşırıqların icra nəticələrini alır.
Proqramın icrası üçün tələb olunan köməkçi prosessor çağırışlarının minimal sayını tapın.
Giriş məlumatları:
Birinci sətir N və M (1 ≤ N, M ≤ 2·10^5) – tapşırıqların sayı və onların arasındakı asılılıqların sayını ehtiva edir.
İkinci sətir N ədəd E[i] ∈ {0,1}, boşluqlarla ayrılmışdır. Əgər E[i] = 0 olarsa, i tapşırığı əsas prosessorda icra olunmalıdır, əks halda köməkçi prosessorda icra olunmalıdır.
Növbəti M sətir tapşırıqlar arasındakı asılılıqları təsvir edir. Hər bir sətir iki ədəd T[1] və T[2] ehtiva edir, bu o deməkdir ki, T[1] tapşırığı T[2] tapşırığından asılıdır (T[1] ≠ T[2]). Tapşırıqlar 0-dan N-1-ə qədər nömrələnib. Bütün M cütlər fərqlidir.
Çıxış məlumatları:
Bir ədəd çıxarın – proqramın icrası üçün lazım olan köməkçi prosessor çağırışlarının minimal sayı.