题目描述

小蓝最近迷上了一款收集宝石的游戏, 在游戏中给出了一幅藏宝图, 藏宝图可以看做是由 $n$ 个顶点组成的一个有向图, 顶点编号为 $0,1,2,⋯,n-1$。每个顶点有且仅有一颗宝石, 可能是红宝石或蓝宝石。

小蓝有一次收集宝石的机会, 他可以任意选择一个顶点当做起点, 沿着有向边前进, 经过的顶点上的宝石都会被自动收集（包括起点和终点）, 直到前方无路可走或者小蓝想退出时停止本次收集。

小蓝可以多次经过同一个顶点, 但只会在第一次到达顶点时获得宝石, 后面再次到达时不会再获得宝石。

收集结束后, 小蓝可以用手中的宝石合成紫晶宝石：一颗红宝石加一颗蓝宝石就可以合成一颗紫晶宝石。

小蓝想在收集结束后合成尽可能多的紫晶宝石, 请帮他规划出一条最优路径, 告诉他最多可以合成多少颗紫晶宝石。

输入格式

输入的第一行包含一个整数 $n$，表示有顶点的个数。

第二行包含一个由 $0$、$1$ 组成的长度为 $n$ 的字符串，从左至右依次表示第 $0$ 至 $n−1$ 个顶点处宝石的种类：

0 表示红宝石，1 表示蓝宝石。

第三行包含一个整数 $m$，表示图中有 $m$ 条有向边。

接下来 $m$ 行，每行包含两个整数 $s$ 和 $t$，用一个空格分隔，表示一条从 $s$ 到 $t$ 的有向边。

输出格式

输出一行包含一个整数，表示小蓝最多能合成几颗紫晶宝石。

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

2

解释 #1

选择 $0$ 号顶点作为起点，按照 $0→1→2→3→1→2→4$ 的行进路线，可以获得 $3$ 颗红宝石和 $2$ 颗蓝宝石，最终可以合成 $2$ 颗紫晶宝石；

他也可以按照 $1→2→3→1→2→4$ 行进，结果也是 $2$。找不到比 $2$ 更大的答案了。

数据范围

对于所有的评测用例：$1 ≤ n ≤ 2000,0 ≤ m ≤ 10^5,0 ≤ s ≤ n−1,0 ≤ t ≤ n−1$