問題
Ksansansan君たち$K$人は街$C$の中で、遊ぶことになりました。そこで最適な集合場所を決めることになりました。
最適な集合場所とは以下の通りです。
条件 スタートから集合までにかかる時間が最も少ない
ただし、全員1分で1地点進める。
集合までにかかる時間を出力しなさい。
不明な点があったら本人に直接言ってね。
入力
入力は以下の形式で標準入力から与えられる。
$N M K$ $A_1 A_2 … A_K$ $X_1 Y_1$ $X_2 Y_2$ : $X_M Y_M$
1行目に整数$N M K$が与えられる。
$N$は街の地点の数
$M$は街の辺の数
$K$は街の遊ぶ人数を表す。
2行目に数列$A$が与えられる。
数列$A_i$は$人i$の家の地点番号を表す。
3行目以降に整数$X_i Y_i$が与えられる。
整数$X_i Y_i$は$地点X_iと地点Y_i$がつながっていることを表す。
出力
$ANS$出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 10^{4}$
- $0 \leq M \leq 10^{4}$
- $1 \leq K \leq min(N,10^{3})$
- $1 \leq X_i,Y_i \leq N$ ただし、この問題は必ず集合できます。
入出力例
入力例1
4 3 3 1 2 3 1 4 2 4 3 4
出力例1
1