问题 22929. -- 细胞变异

22929: 细胞变异

时间限制: 2 Sec  内存限制: 128 MB
献花: 6  解决: 1
[献花][花圈]

题目描述

 

苏八八今天又早起做实验啦。最近他发现几个新品种细胞的转换规律,他们每隔一天就会自主地进行彼此间的转换,比如1细胞进行一天的变异就可能变成2细胞、3细胞,当然也可能不发生变异。如果1细胞变异时经过了K个细胞,则这个细胞中遗留的KDNA片段会相互作用,只需一小会儿(这段时间忽略不计)这kDNA片段就会让这细胞转换成变异细胞X

苏八八想得到一种变异细胞X,而今天现在实验室里只储备了大量的1细胞。所以苏八八向小伙伴的你求助,希望知道如果今天他开始培育1细胞,至少要等待几天能观察到细胞X

为了简化问题,我们给细胞用数字1-n编号。

输入

 

第一行输入3个整数n, m,K( 1<=n<=200,0<=m<=1000, 1<=K<=min(10,n) ).表示一共有n种细胞,m种转换可能,K描述如上。

第二行输入K个整数表示拥有这K个特定DNA片段的细胞编号。

下面m行,每行2个整数u, v( 1<=u,v<=n ). 表示u细胞可以转换到v细胞。

输出

 

输出一个整数表示最少需要的转换天数,如果无法产生细胞X,则输出-1.

样例输入

2 1 2
1 2
1 2

2 0 2
1 2

6 6 1
2
1 2
2 3
1 3
3 4
4 5
5 6

样例输出

1
-1
1

提示

来源

[献花][花圈]