Speedrun
Contest: Pinely Round 2 (Div. 1 + Div. 2)
Difficulty rating: 2100
Tags: brute force, dfs and similar, dp, graphs, greedy, math, sortings, two pointers

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 format:
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 format:
For each test case, output a single integer — the minimum completion time.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
24
7
0
480
5
8

Editorial:
First of all, assume that the first quest we complete is at the hour $$$x$$$. We can assume that $$$0\leq x < k$$$, as increasing it by $$$k$$$ just shifts all the times by $$$k$$$. In this case one can greedily find the completion times for all the quests: essentially, for every quest $$$v$$$, if we know that the quests it depends on are completed at hours $$$c_1$$$, ..., $$$c_d$$$, then the quest $$$v$$$ cannot be completed earlier than $$$\max(c_1, \ldots, c_d)$$$. So if we define $$$f(x, y)$$$ to be the smallest $$$z\geq x$$$ such that $$$z\equiv y\pmod{k}$$$, then the completion time of $$$v$$$ is $$$f(\max(c_1, \ldots, c_d), h_v)$$$. If the quest $$$v$$$ does not depend on anything, then, obviously, the time if simply $$$f(x, h_v)$$$.
The problem is that we don't know which starting time $$$x$$$ is optimal. On the other hand, we know that it can be assumed to be from $$$[0, k)$$$. Also, there is no sense in $$$x$$$ not being $$$h_v$$$ for any quest $$$v$$$ without incoming dependencies. So we can do the following: first assume that $$$x = 0$$$ and find all the completion times for the quests, denote them by $$$c_i$$$. Then consequently increase $$$x$$$ until it becomes $$$k$$$.
Sometimes $$$x$$$ becomes equal to some $$$h_v$$$ where $$$v$$$ is a quest that could theoretically be completed first. At these moments we know that the answer is no more than $$$\max c_i - x$$$. When we increase $$$x$$$ again, such quests can no longer have $$$c_i = x$$$, and thus some values $$$c_i$$$ increase by some multiple of $$$k$$$.
However, for $$$x = k$$$ all $$$c_i$$$ are exactly $$$k$$$ more than when $$$x = 0$$$. Therefore, each value of $$$c_i$$$ in this process increases exactly once and exactly by $$$k$$$. Now there are two ways to finish the solution.
1. Sort all events of type "some $$$c_i$$$, where quest $$$i$$$ doesn't have incoming dependencies, increase by $$$k$$$". For each such event, we run DFS from such vertices to see if some the quests depending on them must also be completed $$$k$$$ hours later. One can see that this DFS will be run from each vertex exactly once throughout the process, thus resulting in $$$O(n + m)$$$ time complexity.
2. When building all $$$c_i$$$ the first time, also find for each vertex $$$v$$$ the first $$$x$$$ when its $$$c_v$$$ must change. If we denote it with $$$w_v$$$ then it can be expressed as $$$\max\{w_u\,\colon\,u\to v, c_u + k > c_v\}$$$. Then sort all events of type "some $$$c_i$$$, where quest $$$i$$$ may or may not have incoming dependencies, increase by $$$k$$$".
In both approaches one can easily maintain $$$\max c_i$$$ as this value can only increase.