CF1863E.Speedrun
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 hj of a game day. The game day is k hours long. The hours of each game day are numbered 0,1,…,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 (ai,bi) the bi -th quest can only be completed after the ai -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.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤100000 ). The description of the test cases follows.
The first line of each test case contains three integers n , m , and k ( 1≤n≤200000 , 0≤m≤200000 , 1≤k≤109 ) — 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 h1,h2,…,hn ( 0≤hi<k ).
The next m lines describe the dependencies. The i -th of these lines contains two integers ai and bi ( 1≤ai<bi≤n ) meaning that quest bi can only be completed after quest ai . It is guaranteed that all dependencies are pairwise distinct.
It is guaranteed that the sum of n over all test cases does not exceed 200000 .
It is guaranteed that the sum of m over all test cases does not exceed 200000 .
输出格式
For each test case, output a single integer — the minimum completion time.
输入输出样例
输入#1
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
输出#1
24 7 0 480 5 8
说明/提示
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 .