SP2422 JAZZYJOB - Jazzy Job

随着能源危机的日益加剧，化学家们决定重新研究各种化学物质的制备过程。 在这个项目中，他们列出了通常用作原材料的元素（初始反应物）以及希望获得的最终产物。同时，他们也准备了一份详细的已知化学反应和转化过程的列表，用于将一种物质转化为另一种物质。 一个主要问题是，许多反应启动时需要的能量过于庞大。他们希望在设计新流程时，将所需的活化能保持在较低水平。 了解这些情况后，他们试图找到制备目标物质的方法： 1. 在所有可能的路径中，确保任一反应所需的最大活化能不超过给定的上限值。 2. 在所有（初始反应物）→（最终产物）的路径中，尽可能减少化学反应或过程的总次数。 每种物质在接受特定能量后都会转化成另一种物质。对于一个特定的能量值，生成的物质是唯一的。每个生成目标物质（最终产物）的过程，只从某个源物质开始，并且不产生副产物。 你的任务是找出一个最小的上限值，使得所有的最终产物都能在这个上限值的条件下获得，并在这个条件下，计算出获得所有最终产物所需的最小转换次数。 **注意：** 所有过程默认是不可逆的，除非特别说明。如若过程可逆，其能量需求可能相同，亦可能不同。你可以假设初始反应物的供应是无限的。

第一行输入一个整数 $t$，表示测试用例的数量。每个测试用例的第一行包含三个整数：初始反应物数量 $S$、最终产物数量 $D$ 和总元素数量 $N$。接下来的 $S+D$ 行中，前 $S$ 行给出初始反应物的 ID（从 0 开始），接下来的 $D$ 行给出最终产物的 ID（从 0 开始）。然后，输入一行包含一个整数 $R$，表示可能的化学反应数量。接下来的 $R$ 行中，每行包含三个整数：物质 $S$、转化后的物质 $C$ 和该化学反应所需的活化能 $A$。$0 \le S, C < N$。

对于每个测试用例，在单独的一行中输出两个整数 $(a, b)$，用空格隔开，其中 $a$ 是最小的上限值，$b$ 是与 $a$ 相对应的最小转换次数。如果对于任何上限值不能获得所有的最终产物，输出一行 "Excessive Energy."。

- $1 \le t \le 10$ - $1 \le S, D \le 100$ - $1 \le N \le 1000$ - $1 \le R \le 10000$ - $0 \le A \le 10^9$ **本翻译由 AI 自动生成**