极速通关

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

一天有 $k$ 小时，任务 $i$ 只能在每天第 $h_i$ 小时完成。给定无环依赖 $a\to b$，任务 $b$ 必须在 $a$ 之后完成；同一小时可完成任意多个满足依赖的任务。求最后任务与最先任务完成时刻之差的最小值。

输入格式

第一行包含测试组数 $t$。每组给出 $n,m,k$、数组 $h$ 和 $m$ 条依赖。依赖满足 $a<b$。所有测试组的 $n$ 之和、$m$ 之和分别不超过 $2\cdot10^5$。

输出格式

每组输出一个整数。

样例输入 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

数据范围

• $1\le t\le10^5$，$1\le n\le2\cdot10^5$，$0\le m\le2\cdot10^5$，$1\le k\le10^9$；
• $0\le h_i<k$，依赖边满足 $1\le a<b\le n$；
• 所有测试组的 $n$ 之和、$m$ 之和分别不超过 $2\cdot10^5$。