Under construction

Still being built. Things may change

Cosmic Commute

Interview

Time limit3sMemory limit1024 MB

Summary
Find the expected minimum number of light trains from planet 1 to planet n when one random wormhole teleport is allowed.
Level

Medium5 of 10

Topics
BFS, Graph, Math
Solved
No attempts yet

Problem

A long time ago, in a galaxy far, far away, the InterCosmic Passage Company (ICPC) runs a complex railway system using light trains. Each planet has exactly one train station, and each light train connects two distinct planets, running back and forth between them. Recently, ICPC launched a teleportation system that is still in its testing phase. Some train stations have a wormhole. All wormholes are connected to each other, so you can teleport from one wormhole to another instantly. To avoid overloading the new system, each citizen of the galaxy may teleport at most once a day.

Charlie lives on Gallifrey and works on Sontar. It is her first day at work, and she is already very late because her alarm clock did not go off. Today the new teleportation system is malfunctioning, so she cannot choose the destination wormhole. Instead, after she enters a wormhole, she is teleported to a wormhole chosen uniformly at random from all the other wormholes. (She never ends up at the same train station after teleporting.)

Charlie is determined to get to work on time. All light trains are very slow, so she wants to take as few light trains as possible. If she can use the malfunctioning teleportation system at most once, what is the expected minimum number of light trains she has to take to get to work?

Input

The first line contains integers n,m,kn, m, k (2≤n≤2⋅1052 \leq n \leq 2\cdot10^5, n−1≤m≤106n - 1 \leq m \leq 10^6, 2≤k≤n2\leq k\leq n): the number of planets, light trains, and planets with a wormhole. Planet 11 is Charlie's home planet Gallifrey, and planet nn is Sontar, where Charlie works.

The second line contains kk distinct integers, the planets whose train stations each have a wormhole.

The next mm lines each contain two integers aa and bb (1≤a,b≤n1 \leq a,b \leq n, a≠ba \neq b), describing a light train between planets aa and bb. All light trains are pairwise disjoint. It is guaranteed that you can travel from any planet to any other planet using only light trains.

Output

Output a single reduced fraction, the expected minimum number of light trains Charlie has to take to get to work if she can use the malfunctioning teleportation system at most once. Print the fraction as "a/b", where aa is the numerator and bb is the denominator.

Examples2

  1. Example 1

    Input
    5 5 3
    2 3 4
    1 2
    1 3
    2 4
    3 4
    4 5
    
    Expected output
    5/2
    
  2. Example 2

    Input
    5 6 3
    2 3 4
    1 2
    1 3
    2 4
    3 4
    4 5
    1 4
    
    Expected output
    2/1