Задача Vinsoft. В г. Винница есть N фирм, занимающихся разработкой программного обеспечения. Известный винницкий олигарх Чайник решил монополизировать отрасль в городе, создав концерн Vinsoft. Для этого он решил приобрести как можно больше фирм. Он разослал соответствующие предложения всем N компаниям и через некоторое время получил от каждой из них согласие или отказ. Но, как опытный бизнесмен, Чайник знает, что в бизнесе очень многое зависит от взаимного доверия партнеров. Путем сбора информации Чайник обнаружил, между которыми фирмами существует взаимное доверие (причем, всегда, если фирма A доверяет фирме B, то фирма B доверяет фирме A). Теперь Чайник может повторно разослать предложения всем фирмам, включив в письмо список фирм, которые согласились на его проект. При этом каждая фирма, независимо от своей первоначальной позиции, дает согласие, если в списке есть хоть одна фирма, которой она доверяет, и отказывается в противном случае. Таким образом, некоторые фирмы, которые изначально не соглашались, теперь дают согласие «продаться» Чайнику, а некоторые из тех, что сначала дали согласие, отказываются. В результате в Чайника формируется новый список, он снова может разослать фирмам. Такую операцию Чайник может повторять много раз, каждый раз рассылая текущий список. Он может прекратить процесс в любой момент и приобрести те фирмы, которые после последнего рассылки согласились. Какое максимальное число фирм может купить Чайник? Как это ни странно, Чайник - честный олигарх и никогда не «подтасовывает» списки.
Технические условия. Программа Vinsoft читает с устройства стандартного ввода в первой строке число N - количество фирм (1≤N≤2000). Далее в той же строке N чисел, описывающих ответ компании на первое предложение Чайника (1 - согласие 0 - отказ). Далее - число M (0≤M≤200000) - количество пар компаний, между которыми существует доверие. Далее - M пар чисел, задающих номера фирм, между которыми существует взаимное доверие (числа в паре не могут быть одинаковыми). Любая пара фирм упоминается в списке не более одного раза. Все числа разделены пробелами. Программа выводит на устройство стандартного вывода максимальное число фирм, которые сможет купить Чайник.
Примеры
|
Ввод |
|
7 1 0 0 0 0 0 1 6 1 2 1 3 1 4 4 5 5 6 2 5 Вывод 4 |
|
Ввод 3 0 0 0 0 Вывод 0 |