P13668 [GCPC 2023] Cosmic Commute

很久很久以前，在一个遥远的星系中，星际通道公司（ICPC）运营着一个复杂的铁路系统，使用着“光速列车”。 :::align{center}  盖利弗雷上方的虫洞，图片来源：[mau\_king](https://pixabay.com/de/photos/milchstra\%c3\%9fe-wurmloch-5904640/) ::: 每个星球恰好有一个火车站，每列光速列车连接两个不同的星球，并在它们之间往返运行。 最近，星际通道公司建立了一个传送系统，目前正处于测试阶段。 一些火车站现在扩建了一个“虫洞”。 所有虫洞彼此相连，可以瞬间从一个虫洞传送到另一个虫洞。 为了不让新系统过载，每个星系公民每天最多只能使用一次传送。 查理住在盖利弗雷星球，在桑塔星球工作。 今天是她第一天上班，但她已经迟到了，因为她愚蠢的闹钟没有响。 更糟糕的是，今天偏偏传送系统还出现了故障，无法选择目的地虫洞。 现在，进入虫洞后，会被随机传送到所有其他虫洞中的某一个（每个虫洞被选中的概率相同）。 （不可能在传送后还停留在同一个火车站。） 尽管运气很差，查理还是决心按时到达公司。 由于所有光速列车都很慢，她希望乘坐尽可能少的光速列车。 如果她最多只能使用一次（故障的）传送系统，求她到达公司的最小期望乘坐光速列车次数。

输入包含： - 一行三个整数 $n, m, k$（$2 \leq n \leq 2\cdot10^5$，$n-1 \leq m \leq 10^6$，$2 \leq k \leq n$），分别表示星球数、光速列车数和虫洞数。第 $1$ 号星球是查理的家（盖利弗雷），第 $n$ 号星球是她工作的地方（桑塔）。 - 一行 $k$ 个互不相同的整数，表示每个拥有虫洞的星球编号（这些火车站除了光速列车外还拥有虫洞）。 - 接下来 $m$ 行，每行两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$ 且 $a \neq b$），表示在星球 $a$ 和 $b$ 之间有一列光速列车。保证所有光速列车两两不同。 - 保证仅使用光速列车可以从任意星球到达任意其他星球。

输出一个最简分数，表示查理在最多使用一次（故障的）传送系统的情况下，到达公司的最小期望乘坐光速列车次数。 输出格式为“$\texttt{a/b}$”，其中 $a$ 是分子，$b$ 是分母。

由 ChatGPT 4.1 翻译