问题描述

给定一个有 $N$ 个顶点和 $M$ 条边的有向图。每个顶点 $i$ 上都有一个整数 $X_i$。喜欢玩游戏的兄妹准备使用这个图和一个棋子来进行游戏。

• 初始时，棋子放在顶点 $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 \leq N \leq 100,000$）和边的个数 $M$（$1 \leq M \leq 200,000$）。
• 第 $2$ 行包含 $N$ 个整数，用空格分隔，表示每个顶点上的整数。其中第 $i$（$1 \leq i \leq N$）个整数 $X_i$（$0 \leq X_i \leq 10^9$）表示顶点 $i$ 上的整数。
• 接下来的 $M$ 行描述边的信息。其中第 $i$（$1 \leq i \leq M$）行包含两个整数 $A_i$ 和 $B_i$，用空格分隔，表示从顶点 $A_i$ 到顶点 $B_i$ 存在一条有向边。保证不存在重复的边，即对于任意 $p \neq q$，有 $A_p \neq A_q$ 或者 $B_p \neq B_q$。

子任务

本问题设有部分分。

• 对于满足 $N \leq 1000$ 和 $M \leq 2000$ 的数据集 $1$，答案正确可以获得 $30$ 分。
• 对于所有测试用例答案正确可以额外获得 $70$ 分。

输出格式

输出到标准输出，末尾必须包含换行符。

输出游戏的得分。

示例 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$。