问题描述

小蓝最近迷上了一款收集宝石的游戏, 在游戏中给出了一幅藏宝图, 藏宝图可以看做是由 $n$ 个顶点组成的一个有向图, 顶点编号为 $0,1,2, \cdots, 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

样例说明

样例如上图所示, 选择 0 号顶点作为起点, 按照 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$ 的行进路线, 可以获得 3 颗红宝石和 2 颗蓝宝石, 最终可以合成 2 颗紫 晶宝石; 他也可以按照 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$ 行进, 结果也是 2 。找不到比 2 更大的答案了。

评测用例规模与约定

对于所有的评测用例, $1 \leq n \leq 2000,0 \leq m \leq 10^{5}, 0 \leq s \leq n-1, 0 \leq t \leq n-1$。