Cosmic Commute
InterviewTime limit3sMemory limit1024 MB
Find the expected minimum number of light trains from planet 1 to planet n when one random wormhole teleport is allowed.
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 (, , ): the number of planets, light trains, and planets with a wormhole. Planet is Charlie's home planet Gallifrey, and planet is Sontar, where Charlie works.
The second line contains distinct integers, the planets whose train stations each have a wormhole.
The next lines each contain two integers and (, ), describing a light train between planets and . 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 is the numerator and is the denominator.