1. Vinsoft

Задача Vinsoft В м. Вінниця є N фірм,  що займаються  розробкою програмного забезпечення. Відомий вінницький олігарх  Чайник  вирішив монополізувати галузь в місті, створивши концерн Vinsoft. Для цього він вирішив придбати як  можна  більше фірм . Він розіслав відповідні пропозиції   всім N компаніям і через деякий час отримав від кожної з них згоду або відмову. Але, як досвідчений бізнесмен, Чайник знає, що  в бізнесі дуже багато залежить  від  взаємної довіри партнерів.

Шляхом збирання інформації Чайник виявив, між  якими фірмами існує взаємна довіра (причому, завжди, якщо фірма A довіряє  фірмі B, то фірма B довіряє фірмі A).

Тепер  Чайник може повторно розіслати пропозиції всім фірмам, включивши до листа список фірм, що погодилися на його проект. При цьому кожна фірма, незалежно від своєї початкової позиції, дає згоду, якщо  в списку є хоч одна фірма, якій вона довіряє, і відмовляється  в іншому випадку. Таким чином, деякі фірми, які спочатку  не погоджувались, тепер дають згоду «продатися» Чайнику,  а деякі із тих, що спочатку дали згоду, відмовляються. В результаті у Чайника формується  новий список, який він знову може розіслати фірмам. Таку операцію Чайник може повторювати багато разів, щоразу розсилаючи  поточний список. Він може припинити процес в любий момент і придбати ті фірми, які після  останнього розсилання  погодилися. Яке максимальне число фірм може купити Чайник ?.

Як це не дивно, Чайник – чесний олігарх і ніколи не «підтасовує» списки .

Технічні умови. Програма Vinsoft  читає з пристрою стандартного введення у першому рядку    число N — кількість фірм (1≤N≤2000). Далі в  тому ж  рядку  N чисел, що описують відповідь  фірми на першу пропозицію Чайника (1 — згода, 0 — відмова). Далі -  число M (0≤M≤200000) — кількість пар компаній, між якими існує довіра. Далі - M  пар чисел, що задають номери фірм, між якими існує  взаємна довіра (числа в парі не можуть бути однаковими). Будь-яка  пара фірм згадується в списку не більше одного разу. Всі числа розділено пропусками. Програма виводить на пристрій стандартного виведення — максимальне число фірм, які зможе купити Чайник.

Приклади