У Тридесятій державі є \(N\) фірм, які займаються розробкою програмного забезпечення. Якось відомий олігарх Тридесятої держави Степан вирішив монополізувати цю галузь. Для цього він хоче купити максимальну кількість програмістських фірм Тридесятої держави.

Він розіслав пропозиції всім \(N\) компаніям і через деякий час отримав від кожної з них згоду або відмову. Однак він знає, що у бізнесі дуже багато залежить від взаємної довіри партнерів. В результаті невеликого дослідження Степан встановив, між якими компаніями існує взаємна довіра (причому якщо компанія довіряє компанії \(B\), то компанія \(B\) довіряє компанії \(A\)).

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

Напишіть програму, яка визначить, яку максимальна кількість компаній може об'єднати Степан під своїм керівництвом.

Вважатимемо, що Степан — чесний підприємець і він ніколи не підтасовує списки, що йому розсилаються.

Формат вхідних даних

У першому рядку вхідних даних міститься число \(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