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

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

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

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

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

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

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

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

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

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

2

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

對于所有的評測用例，1 ≤ n ≤ 2000 ，0 ≤ m ≤ 10⁵ ，0 ≤ s ≤ n ? 1 ，0 ≤ t ≤ n ? 1。