该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

日语中的“一方通行”也有单行道的意思。

题目描述

由于今年是《魔法禁书目录》出版二十周年，学园都市内的 $n$ 个车站正在举办庆祝活动，为每个过往的行人发纪念徽章。每个车站只有 $1$ 种纪念徽章，而这些纪念徽章共有 $k$ 种。

很可惜，连接这 $n$ 个车站的 $m$ 条线路都是单向通行。为了防止部分人多次到访同一个站点，管理人员在设置线路的时候就保证不会出现环。

$\mathtt{Zoomy}$ 现在在 $1$ 号站点，可以任意选择终点。请你计算 $\mathtt{Zoomy}$ 最多拿到多少个同种徽章。

输入格式

第一行三个数 $n,m,k$。

第二行 $n$ 个数 $a_i$，表示第 $i$ 个站点拥有的徽章类型。

之后的 $m$ 行每行两个数 $u,v$，代表一条从 $u$ 到 $v$ 的单行道。

输出格式

一个数，表示同种徽章数量的最大值。

样例 #1

样例输入 #1

5 7 2
1 2 2 1 1
1 2
1 4
4 2
2 3
4 3
3 5
1 5

样例输出 #1

3

样例 #2

样例输入 #2

5 4 3
1 2 3 1 2
1 2
2 3
3 4
4 5

样例输出 #2

2

请注意，该组样例满足 SubTask 2 的条件。

样例 #3

样例输入 #3

5 4 5
1 2 3 4 5
1 2
1 3
1 4
1 5

样例输出 #3

1

请注意，该组样例满足 SubTask 1 的条件。

数据范围

对于 $5\%$ 的数据，$n=2$；

对于 $20\%$ 的数据，$n\le 10$；

对于另外 $10\%$ 的数据，$m=n-1$ 且第 $i$ 条边连接 $1$ 与 $i$；(SubTask 1 捆绑测试)

对于另外 $30\%$ 的数据，$m=n-1$ 且第 $i$ 条边连接 $i$ 与 $i+1$；(SubTask 2 捆绑测试)

对于全部的数据，$n\le 10^5,m\le \min\{\dfrac{n\times (n-1)}{2},5 \times 10^5\}, k\leq 10$。

powered by Zoomy