小藍(lán)最近迷上了一款收集寶石的游戲，在游戲中給出了一幅藏寶圖，藏寶圖可以看做是由 n 個(gè)頂點(diǎn)組成的一個(gè)有向圖，頂點(diǎn)編號(hào)為 0, 1, 2, · · · , n ? 1。每個(gè)頂點(diǎn)有且僅有一顆寶石，可能是紅寶石或藍(lán)寶石。

小藍(lán)有一次收集寶石的機(jī)會(huì)，他可以任意選擇一個(gè)頂點(diǎn)當(dāng)做起點(diǎn)，沿著有向邊前進(jìn)，經(jīng)過的頂點(diǎn)上的寶石都會(huì)被自動(dòng)收集（包括起點(diǎn)和終點(diǎn)），直到前方無路可走或者小藍(lán)想退出時(shí)停止本次收集。小藍(lán)可以多次經(jīng)過同一個(gè)頂點(diǎn)，但只會(huì)在第一次到達(dá)頂點(diǎn)時(shí)獲得寶石，后面再次到達(dá)時(shí)不會(huì)再獲得寶石。

收集結(jié)束后，小藍(lán)可以用手中的寶石合成紫晶寶石：一顆紅寶石加一顆藍(lán)寶石就可以合成一顆紫晶寶石。

小藍(lán)想在收集結(jié)束后合成盡可能多的紫晶寶石，請幫他規(guī)劃出一條最優(yōu)路徑，告訴他最多可以合成多少顆紫晶寶石。

輸入的第一行包含一個(gè)整數(shù) n，表示有頂點(diǎn)的個(gè)數(shù)。

第二行包含一個(gè)由 0、1 組成的長度為 n 的字符串，從左至右依次表示第 0 至 n ? 1 個(gè)頂點(diǎn)處寶石的種類，0 表示紅寶石，1 表示藍(lán)寶石。

第三行包含一個(gè)整數(shù) m ，表示圖中有 m 條有向邊。

接下來 m 行，每行包含兩個(gè)整數(shù) s, t ，用一個(gè)空格分隔，表示一條從 s 到 t 的有向邊。

輸出一行包含一個(gè)整數(shù)，表示小藍(lán)最多能合成幾顆紫晶寶石。

6
000111
6
0 1
1 2
3 1
2 3
2 4
2 5

2

樣例如上圖所示，選擇 0 號(hào)頂點(diǎn)作為起點(diǎn)，按照 0 → 1 → 2 → 3 → 1 → 2 → 4 的行進(jìn)路線，可以獲得 3 顆紅寶石和 2 顆藍(lán)寶石，最終可以合成 2 顆紫晶寶石；他也可以按照 1 → 2 → 3 → 1 → 2 → 4 行進(jìn)，結(jié)果也是 2 。找不到比 2 更大的答案了。

對(duì)于所有的評(píng)測用例，1 ≤ n ≤ 2000 ，0 ≤ m ≤ 105 ，0 ≤ s ≤ n ? 1 ，0 ≤ t ≤ n ? 1。