CF1863E Speedrun

你正在玩一款电子游戏。游戏中有 $n$ 个任务需要完成。然而，第 $j$ 个任务只能在游戏日的第 $h_j$ 小时开始时完成。一个游戏日共有 $k$ 小时。每个游戏日的小时编号为 $0, 1, \ldots, k-1$。第一天结束后，新的游戏日开始，如此循环。 此外，任务之间存在依赖关系，即对于某些对 $(a_i, b_i)$，第 $b_i$ 个任务只能在完成第 $a_i$ 个任务之后才能完成。保证不存在环状依赖，否则游戏将无法通关，也就没人玩了。 你足够熟练，可以在极短的时间内完成任意数量的任务（也就是说，即使任务之间存在依赖关系，你也可以在同一小时的开始时完成任意数量的任务）。你希望尽快完成所有任务。为此，你可以以任意合法顺序完成任务。完成时间定义为完成最后一个任务的时间与完成第一个任务的时间之差。 请你计算完成游戏所需的最少时间。

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1\le t\le 100\,000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1\le n\le 200\,000$，$0\le m\le 200\,000$，$1\le k\le 10^9$），分别表示任务数、依赖关系数和每个游戏日的小时数。 下一行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$0\le h_i < k$）。 接下来的 $m$ 行描述依赖关系。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1\le a_i < b_i\le n$），表示任务 $b_i$ 只能在完成任务 $a_i$ 之后才能完成。保证所有依赖关系两两不同。 保证所有测试用例中 $n$ 的总和不超过 $200\,000$。 保证所有测试用例中 $m$ 的总和不超过 $200\,000$。

对于每个测试用例，输出一个整数，表示最小完成时间。

在第一个测试用例中，任务 $1$ 和 $4$ 必须在一天的第 $12$ 小时开始时完成，但它们不能在同一小时内完成，因为你还需要在它们之间完成任务 $2$ 和 $3$。不过你可以在 $24$ 小时内完成所有任务。具体做法是：你在第一天的第 $12$ 小时开始完成第一个任务。第 $16$ 小时完成任务 $2$。第 $18$ 小时完成任务 $3$。最后在第二天的第 $12$ 小时完成任务 $4$。总共耗时（从完成第一个任务到完成最后一个任务）为 $24$ 小时。 在第三个测试用例中，你可以先完成第一个任务，然后立刻完成剩下的任务。你在第一天的第 $5$ 小时完成第一个任务，之后第二个任务变得可用，你也立刻完成它。总共耗时为 $0$。 在第四个测试用例中，你可以从第三个任务开始。你在第一天的第 $555$ 小时开始，第二天的第 $35$ 小时结束。总共耗时为 $1035-555=480$。 由 ChatGPT 4.1 翻译