310636: CF1863E. Speedrun

E. Speedruntime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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 < 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 < 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$.

Output

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

ExampleInput

6
4 4 24
12 16 18 12
1 2
1 3
2 4
3 4
4 3 10
2 6 5 9
1 4
2 4
3 4
2 1 10
5 5
1 2
5 0 1000
8 800 555 35 35
5 0 10
3 2 5 4 7
3 2 5
4 3 2
1 2
2 3

Output

24
7
0
480
5
8

Note

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$.

题目大意：
你正在玩一个视频游戏，游戏有n个需要完成的任务。但是，第j个任务只能在游戏日的第h_j小时开始时完成。游戏日长k小时，每天的小时数为0, 1, ..., k-1。第一天结束后，新的一天开始，依此类推。

任务之间也存在依赖关系，即对于某些(a_i, b_i)对，必须在完成第a_i个任务之后才能完成第b_i个任务。保证没有循环依赖，否则游戏将无法通关。

你足够熟练，可以在可忽略的时间内完成任意数量的任务（即你可以在同一小时开始时完成任意数量的任务，即使它们之间存在依赖关系）。你想尽可能快地完成所有任务。为此，你可以以任何有效的顺序完成任务。完成时间等于按此顺序完成最后一个任务的时间与完成第一个任务的时间之差。

找出完成游戏所需的最少时间。

输入输出数据格式：
每个测试用例包含多个测试案例。第一行包含测试案例数t(1≤t≤100,000)。接下来是测试案例的描述。

每个测试案例的第一行包含三个整数n、m和k(1≤n≤200,000，0≤m≤200,000，1≤k≤10^9)——任务数、任务之间的依赖关系数和游戏日的小时数。

下一行包含n个整数h_1, h_2, ..., h_n(0≤h_i
接下来m行描述依赖关系。第i行包含两个整数a_i和b_i(1≤a_i
保证所有测试案例的n之和不超过200,000。

保证所有测试案例的m之和不超过200,000。

对于每个测试案例，输出一个整数——最小完成时间。题目大意： 你正在玩一个视频游戏，游戏有n个需要完成的任务。但是，第j个任务只能在游戏日的第h_j小时开始时完成。游戏日长k小时，每天的小时数为0, 1, ..., k-1。第一天结束后，新的一天开始，依此类推。 任务之间也存在依赖关系，即对于某些(a_i, b_i)对，必须在完成第a_i个任务之后才能完成第b_i个任务。保证没有循环依赖，否则游戏将无法通关。 你足够熟练，可以在可忽略的时间内完成任意数量的任务（即你可以在同一小时开始时完成任意数量的任务，即使它们之间存在依赖关系）。你想尽可能快地完成所有任务。为此，你可以以任何有效的顺序完成任务。完成时间等于按此顺序完成最后一个任务的时间与完成第一个任务的时间之差。 找出完成游戏所需的最少时间。 输入输出数据格式： 每个测试用例包含多个测试案例。第一行包含测试案例数t(1≤t≤100,000)。接下来是测试案例的描述。 每个测试案例的第一行包含三个整数n、m和k(1≤n≤200,000，0≤m≤200,000，1≤k≤10^9)——任务数、任务之间的依赖关系数和游戏日的小时数。 下一行包含n个整数h_1, h_2, ..., h_n(0≤h_i