#P5247. 「2019-05-06提高模拟赛」维修(servicing)

「2019-05-06提高模拟赛」维修(servicing)

Description

    T 公主初至 Y 国,见道旁高耸,山谷幽幽,而百姓和乐,民风淳朴,道不拾遗,夜不闭户,宛若欲界之仙都。大喜,居焉,乐不思蜀,俄而十有五载。
    得归,父大喜,T 公主以 Y 主治告之,遂学其政。高祖乃止休养,却生息,持新政,颁国法,励工农,兴贾商。民闻 T 公主,无不称赞其议。     ——『T 国本纪』

Tweetuzki 来到 Y 国后,被这里人民的热情,崇高的道德所吸引,在 Y 国待了长达 15 年之久。看到所有百姓衣食无忧的生活,Tweetuzki 公主十分感慨。在这 15 年之中,她充分体会到了 Y 国国君 <font color"black">C</font>hangyu 的政治智慧,有了许多心得。但是 Tweetuzki 不随便与人交流自己的心得,Tweetuzki 喜欢与厉害的人交往,如果你在由 XieRujian 出版的《Tweetuzki YC 列传》系列比赛中连续 33AK\texttt{AK} 比赛,那么你就能讨得公主的欢心,Tweetuzki 公主就会告诉你她 Y 国之旅的感想。

但是离开 Y 国前,她发现问题很大,她的马车在山谷里行进时就已经有损坏,路途中常常需要维修,但并不是中途所有的驿站都像 Y 国的城市一样先进,其中大部分不设有维修站。一次维修之后,她的马车最多能在不维修的情况下连续地安全行驶过 kk 条大路,如果没有及时停靠在一处设有维修站的驿站的话,她的马车就会不安全。

15 年之后,沧海桑田,世界出现了许多变化。为了计划行走路线,她派人了解了一下 T 国与 Y 国关口之间的驿站,并把它们绘制成一张地图。

Y 国与 T 国之间有 n2n - 2 座驿站,加上 Y 国和 T 国的关口一共就有 nn 处可停留点,有 mm 条可双向通行的大路将它们相连,其中 Y 国关口编号为 SS,T 国关口编号为 TTTweetuzki 公主从 Y 国关口出发到达 T 国关口,其中有 pp 处可停留点设有维修站,并且 Y 国关口处是一定存在维修站的。

由于 T 国宗室十分清廉,善良的 Tweetuzki 公主也一样,但 Tweetuzki 公主不善于精打细算规划路线,她只想知道如果她能安全回到 T 国,她的车每次至少需要维修至多牢固。

Input Format

输入文件名为 servicing.in

输入数据第一行一个自然数 TT,表示测试点编号,便于你获得本题的部分分,你不一定会用到此信息。样例数据的编号为 00
输入数据第二行一个正整数 KK,表示数据组数。
每组测试数据的第一行三个正整数 n,m,pn , m , p,表示可停留点数量,道路数量以及设有维修站的可停留点数量。
第二行 pp 个正整数,分别表示设有维修站可停留点的编号。
接下来 mm 行,每行 22 个整数 u,vu , v,表示一条连接点 uu 和点 vv 的边。
最后一行两个正整数 SSTT,表示 Y 国关口编号和 T 国关口编号。

Output Format

输出文件名为 servicing.out

对于每组数据,如果 Tweetuzki 无法回到 T 国,输出 -1;否则输出一行一个正整数 kk,表示最少在不维修的情况下能连续经过大路的条数。

Sample

样例输入 1

0
2
6 6 3
1 3 6
1 2
2 3
4 2
5 6
4 5
3 4
1 6 
7 10 3
1 3 4
1 2
4 2
7 5
4 5
7 1
2 5
7 2
3 7
3 2
5 1
4 6

样例输出 1

3
-1

样例解释 1

对于第一组数据,我们可以按照 1-2-3-4-5-6 的顺序走到终点,最多连续经过 33 个无维修点的可停留点,可以证明没有更优情况。
对于第二组数据,SSTT 不联通,输出-1

样例 2

见选手目录下servicing文件夹中servicing2.inservicing2.ans

Hint

测试点编号 nn\le mm\le 特殊性质
11 1010 2020 无特殊性质
22
33 200200 2 0002\ 000 答案不超过22
44
55 无特殊性质
66
77
88
99 1 0001\ 000 10 00010\ 000 p=1p=1
1010
1111 无特殊性质
1212
1313 p10p\le10
1414
1515 15 00015\ 000 30 00030\ 000 答案为偶数或负数
1616
1717 无特殊性质
1818
1919 100 000100\ 000 150 000150\ 000
2020

对于所有数据,$K\le 5\ ,\ 1\le S,T\ ,\ S\neq T\ ,\ 1\le u,v,p\le n$。