問題文
N 頂点 M 边的有向图。该图的顶点 i 是一个整数 写入 X_i 。一位热爱游戏的兄妹分享了这张图。 1 我正在尝试使用两个棋子玩游戏。
- 首先,将棋子移到顶部 将其放入 1 。
-
在轮到他时,玩家恰好执行以下操作之一: 1 你必须做两件事。
- 移動 :将棋子精确移动到另一个顶点 移动 1 次。一块在顶部 如果它在 i 中,则顶点 i 到顶点 边指向 j 的顶点 它只能移动到 j 。
- 終了宣言 :结束游戏。
- 轮流交替重复,要么一名玩家宣布结束,要么第二名玩家宣布结束 棋子移动 10^9 次后,游戏立即结束,此时棋子所在顶点处写入的整数 分数 变为。
如果第一个玩家采取行动尽可能增加分数,而第二个玩家采取行动尽可能减少分数,那么游戏的分数是多少?
入力
输入将以以下格式从标准输入给出。
N M X_1 X_2 ... X_N A_1 B_1 A_2 B_2 : A_M B_M
- 1 行包含一个整数,表示图中的顶点数。 N (1 ≦ N ≦ 100,000) 表示边数 M (1 ≦ M ≦ 200,000) 用空格分隔。
- 2 行表示写入每个顶点的整数。 N 整数由空格分隔。其中 i (1 ≦ i ≦ N) 第一个整数 X_i (0 ≦ X_i ≦ 10^9) 是顶点 表示写在 i 中的整数。
- 3 从线 M 行提供边缘信息。其中 i (1 ≦ i ≦ M) 行中,2 整数 A_i,B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i \neq B_i) 用空格分隔。这显示了图中的顶点 指示有一条指向 A_i 到顶点 边指向 B_i 的有向边。然而同一边 它从未被给予 2 次,即 当 p \neq q 什么时候 A_p \neq A_q 或 B_p \neq B_q 保证持有。 满足
部分点
针对此问题设置了部分分数。 如果所有满足
- N ≦ 1000 和 M ≦ 2000 的数据集 如果您正确回答 1 ,30 点。
- 如果所有测试用例都回答正确,除了上述之外 70 点。
出力
游戏得分 在 1 行上输出。在输出末尾插入换行符。
入力例1
3 3 1 3 2 1 2 2 3 3 1
出力例1
2
在此示例中,游戏进行如下。
- 第一个玩家选择移动并将棋子移动到顶部。 移至 1 到顶点 边指向 2 。
- 第二个移动者选择移动并将棋子移动到顶部。 2 到顶点 边指向 3 。
- 第一个玩家选择宣告结束并结束游戏。此时的比分是 2 变为。
无论第一个玩家采取什么行动,第二个玩家都可以通过采取适当的行动来增加分数。 它不能大于 2 。
此外,无论第二个玩家采取什么行动,第一个玩家都可以通过采取适当的行动来增加分数。 它不能小于 2 。
入力例2
4 5 1 3 2 1 1 2 2 3 3 1 2 4 4 3
出力例2
1
在此示例中,游戏进行如下。
- 第一个玩家选择移动并将棋子移动到顶部。 移至 1 到顶点 边指向 2 。
- 第二个移动者选择移动并将棋子移动到顶部。 2 到顶点 边指向 4 。
- 第一个玩家选择移动并将棋子移动到顶部。 移至 4 到顶点 边指向 3 。
- 第二个移动者选择移动并将棋子移动到顶部。 3 到顶点 边指向 1 。
- 第一个玩家选择移动并将棋子移动到顶部。 移至 1 到顶点 边指向 2 。
- 第二个移动者选择移动并将棋子移动到顶部。 2 到顶点 边指向 4 。
- (重复上面的过程一段时间)
- 第二步 10^9 选择第一个棋子并将棋子移动到顶部 3 到顶点 边指向 1 。
- 至此游戏结束,比分为 1 变为。
无论第一个玩家采取什么行动,第二个玩家都可以通过采取适当的行动来增加分数。 它不能大于 1 。
此外,无论第二个玩家采取什么行动,第一个玩家都可以通过采取适当的行动来增加分数。 它不能小于 1 。