CF1863E.Speedrun

You are playing a video game. The game has $n$ quests that need to be completed. However, the $j$-th quest can only be completed at the beginning of hour $h_j$ of a game day. The game day is $k$ hours long. The hours of each game day are numbered $0, 1, \ldots, k - 1$. After the first day ends, a new one starts, and so on.

Also, there are dependencies between the quests, that is, for some pairs $(a_i, b_i)$ the $b_i$-th quest can only be completed after the $a_i$-th quest. It is guaranteed that there are no circular dependencies, as otherwise the game would be unbeatable and nobody would play it.

You are skilled enough to complete any number of quests in a negligible amount of time (i. e. you can complete any number of quests at the beginning of the same hour, even if there are dependencies between them). You want to complete all quests as fast as possible. To do this, you can complete the quests in any valid order. The completion time is equal to the difference between the time of completing the last quest and the time of completing the first quest in this order.

Find the least amount of time you need to complete the game.

你正在玩一款电子游戏。游戏中共有 $n$ 个任务需要完成。然而，第 $j$ 个任务只能在游戏日的第 $h_j$ 小时初完成。每个游戏日共 $k$ 小时，每小时按 $0, 1, \ldots, k - 1$ 编号。第一个游戏日结束后，下一个游戏日立即开始，依此类推。

此外，任务之间存在依赖关系：对某些数对 $(a_i, b_i)$，第 $b_i$ 个任务只能在第 $a_i$ 个任务完成之后才能完成。题目保证不存在环形依赖（否则游戏将无法通关，也就没人会玩了）。

你的操作足够熟练，可以在可忽略不计的时间内完成任意数量的任务（即：你可以在同一小时初完成任意多个任务，即使它们之间存在依赖关系）。你希望以最短时间完成所有任务。为此，你可以按任意满足依赖约束的顺序完成任务。完成时间定义为：最后一个任务的完成时刻与第一个任务的完成时刻之差。

求完成全部任务所需的最短时间。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 100\,000$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1\le n\le 200\,000$, $0\le m\le 200\,000$, $1\le k\le 10^9$) — the number of quests, the number of dependencies between them, and the number of hours in a game day, respectively.

The next line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($0\le h_i \lt k$).

The next $m$ lines describe the dependencies. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1\le a_i \lt b_i\le n$) meaning that quest $b_i$ can only be completed after quest $a_i$. It is guaranteed that all dependencies are pairwise distinct.

It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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 \lt k$）。

接下来的 $m$ 行描述依赖关系。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1\le a_i \lt b_i\le n$），表示任务 $b_i$ 只能在任务 $a_i$ 完成后才能完成。保证所有依赖关系两两不同。

保证所有测试用例中 $n$ 的总和不超过 $200\,000$。

保证所有测试用例中 $m$ 的总和不超过 $200\,000$。

For each test case, output a single integer — the minimum completion time.

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

In the first test case, quests $1$ and $4$ must be completed at the beginning of the $12$-th hour of the day, but they cannot be completed during the same hour, because you also need to complete quests $2$ and $3$ between them. You can do all this in $24$ hours, though. To do so, you start at $12$ hours of the first game day by completing the first quest. At $16$ hours you complete quest $2$. At $18$ hours you complete quest $3$. Finally at $12$ hours of the second day you can complete quest $4$. The total time elapsed (from the moment you completed the first quest and the moment you completed the last) is $24$ hours.

In the third test case, you can complete the first quest and then complete the remaining quest right after. You start at $5$ hours of the first day by completing the first quest. After this the second quest becomes available, you complete it as well. The total time elapsed is $0$.

In the fourth test case, you can start with the third quest. You start at $555$ hours of the first day and you can finish at $35$ hours of the second day. The total time elapsed is $1035-555=480$.

在第一个测试用例中，任务 $1$ 和任务 $4$ 必须在一天的第 $12$ 小时初完成，但它们不能在同一小时内完成，因为你还需要在二者之间完成任务 $2$ 和任务 $3$。不过，你仍然可以在 $24$ 小时内完成所有这些任务。具体做法是：你在游戏第一天的 $12$ 小时开始，完成第一个任务；在 $16$ 小时完成任务 $2$；在 $18$ 小时完成任务 $3$；最后在第二天的 $12$ 小时完成任务 $4$。从完成第一个任务到完成最后一个任务所经过的总时间为 $24$ 小时。

在第三个测试用例中，你可以先完成第一个任务，紧接着立即完成剩余的任务。你于第一天的 $5$ 小时开始并完成第一个任务；此后第二个任务立即解锁，你也随即完成它。总耗时为 $0$。

在第四个测试用例中，你可以从第三个任务开始。你于第一天的 $555$ 小时开始，并于第二天的 $35$ 小时结束。总耗时为 $1035-555=480$。