考古学家 Benjamas 在调查神秘的“鳄鱼地下城”后正在逃命。这座城市有 $N$ 个房间。有 $M$ 条双向走廊，每条走廊连接一对不同的房间。穿过不同的走廊可能需要不同的时间。在 $N$ 个房间中，只有 $K$ 个是允许她逃脱的出口房间。Benjamas 从房间 $0$ 出发。她希望尽快到达一个出口房间。

鳄鱼守门人想要阻止 Benjamas 逃脱。他从自己的巢穴中控制着秘密门，可以封锁任意一条走廊。也就是说，每当他封锁一条新走廊时，之前被封锁的走廊必须重新开放。

Benjamas 的处境可以描述如下：每当她试图离开一个房间时，鳄鱼守门人可以选择封锁该房间相邻的一条走廊。随后，Benjamas 选择并沿着一条未被封锁的走廊前往下一个房间。一旦 Benjamas 进入一条走廊，鳄鱼守门人就不能再封锁它，直到 Benjamas 到达走廊的另一端。一旦她进入下一个房间，守门人可以再次选择封锁一条通往外部的走廊（可能是 Benjamas 刚刚走过的那条），以此类推。

她希望提前制定一个简单的逃生计划。更准确地说，她希望有一套指令，告诉她在到达某个房间时该怎么做。设 $A$ 为其中一个房间。如果它是出口房间，则不需要指令——显然，她可以逃离这座城市。否则，房间 $A$ 的指令应具有以下形式之一：

• “如果你到达了房间 $A$，走通往房间 $B$ 的走廊。然而，如果那条走廊被封锁了，则走通往房间 $C$ 的走廊。”
• “不用管房间 $A$；根据这个逃生计划，你不可能到达它。”

注意，在某些情况下（例如，如果你的计划引导 Benjamas 进入循环），守门人可能能够阻止 Benjamas 到达出口。如果无论守门人做什么，Benjamas 都能保证在有限时间内到达出口，那么这个逃生计划就是“好的”。对于一个好的逃生计划，设 $T$ 为最小的时间，使得在时间 $T$ 之后，Benjamas 保证能到达出口。在这种情况下，我们称这个好的逃生计划耗时 $T$。

编写一个过程 travel_plan(N, M, R, L, K, P)，它接受以下参数：

• $N$ —— 房间数量。房间编号为 $0$ 到 $N-1$。
• $M$ —— 走廊数量。走廊编号为 $0$ 到 $M-1$。
• $R$ —— 一个表示走廊的二维整数数组。对于 $0 \le i < M$，走廊 $i$ 连接两个不同的房间 $R[i][0]$ 和 $R[i][1]$。没有两条走廊连接同一对房间。
• $L$ —— 一个包含穿过走廊所需时间的一维整数数组。对于 $0 \le i < M$，值 $1 \le L[i] \le 1\,000\,000\,000$ 是 Benjamas 穿过第 $i$ 条走廊所需的时间。
• $K$ —— 出口房间的数量。你可以假设 $1 \le K < N$。
• $P$ —— 一个包含 $K$ 个不同条目的一维整数数组，描述出口房间。对于 $0 \le i < K$，值 $P[i]$ 是第 $i$ 个出口房间的编号。房间 $0$ 永远不会是出口房间。

你的过程必须返回存在好的逃生计划的最小时间 $T$。

你可以假设每个非出口房间至少有两条走廊离开它。你还可以假设在每个测试用例中，都存在一个耗时 $T \le 1\,000\,000\,000$ 的好的逃生计划。

样例

输入格式 1

N=5, M=4, K=3
R=[[0,1], [0,2], [3,2], [2,4]]
L=[2, 3, 1, 4]
P=[1, 3, 4]

输出格式 1

7

说明

图 1. 表示带有房间和走廊的地下城的图。

在最坏的情况下，Benjamas 将在 7 个单位时间内到达出口房间。因此，travel_plan 应返回 7。

输入格式 2

N=5, M=7, K=2
R=[[0,2], [0,3], [3,2], [2,1], [0,1], [0,4], [3,4]]
L=[4, 3, 2, 10, 100, 7, 9]
P=[1, 3]

输出格式 2

14

说明

Benjamas 将在不超过 14 个单位时间内到达出口房间之一。因此，travel_plan 应返回 14。

子任务

子任务 1（46 分）

• $3 \le N \le 1\,000$。
• 地下城是一棵树。即 $M = N-1$，且对于每一对房间 $i$ 和 $j$，都有一条连接 $i$ 和 $j$ 的走廊序列。
• 每个出口房间恰好连接到另一个房间。
• 任何其他房间直接连接到三个或更多其他房间。

子任务 2（43 分）

• $3 \le N \le 1\,000$。
• $2 \le M \le 100\,000$。

子任务 3（11 分）

• $3 \le N \le 100\,000$。
• $2 \le M \le 1\,000\,000$。

实现细节

限制

• CPU 时间限制：2 秒
• 内存限制：256 MB
• 注意：没有明确的栈内存大小限制。栈内存计入总内存使用量。

接口 (API)

• 实现文件夹：crocodile/
• 选手需实现：crocodile.c 或 crocodile.cpp 或 crocodile.pas
• 选手接口：crocodile.h 或 crocodile.pas
• 评测接口：crocodile.h 或 crocodilelib.pas
• 示例评测程序：grader.c 或 grader.cpp 或 grader.pas 以及 crocodilelib.pas
• 示例评测输入：grader.in.1, grader.in.2, ...

注意：示例评测程序按以下格式读取输入： 第 1 行：$N, M$ 和 $K$。 第 2 行至 $M+1$ 行：对于 $0 \le i < M$，第 $i+2$ 行包含 $R[i][0], R[i][1]$ 和 $L[i]$，以空格分隔。 第 $M+2$ 行：包含 $K$ 个整数 $P[0], P[1], \dots, P[K-1]$ 的列表，以空格分隔。 第 $M+3$ 行：期望的解。 * 示例评测输入的期望输出：grader.expect.1, grader.expect.2, ... 对于此任务，这些文件中的每一个都应精确包含文本“Correct.”。