蓝桥杯2022年第十三届决赛真题-宝石收集（Python 组）

小蓝最近迷上了一款收集宝石的游戏，在游戏中给出了一幅藏宝图，藏宝图可以看做是由 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

样例如上图所示，选择 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⁵ ，0 ≤ s ≤ n − 1 ，0 ≤ t ≤ n − 1。