The Labyrinth of the Salvataur P64141

(You may consider jumping to the Input section.)

On a particularly hot day in the month of September of year of 20–, I received a letter from my old acquaintance Dr. —, Professor at the Monotechnical University. It was uncommon for him to resort to these means of communication, and the contents of the letter caused me even greater distress. After many years of suspicion fed by rumors and conversations he was not supposed to overhear, he claimed to have found proof of something of the utmost severity concerning our shared alma mater, and instated me to pay him a visit at his office as soon as possible so we could discuss the matter in private. The ominous feeling that the letter planted on me was nothing but multiplied when, guided by the janitor along the colored corridors of the department buildings, we opened the office only to find a toppled chair, drawers and cupboards open, books and papers scattered on the floor—and no sign of the Professor.

However, as soon as the janitor left to warn the corresponding authorities, I swiftly moved next to the desk and pressed the exact location my correspondent had confided to me in a previous encounter. An hidden drawer opened, and there I found a worn-out notebook with a leather cover and a red elastic band wrapped around it. I knew whoever had searched the office and was behind my colleague’s disappearance was certainly looking for this. A few hours later, in a shabby touristic apartment in a seaside neighborhood, I started reading the document, illuminated by candlelight and accompanied by the roar of waves in the sea and the shouts of shirtless drunkards in the street.

However, I was extremely naive to believe my actions of the day had gone unnoticed. Shortly after I laid myself on bed to relieve the pain behind my eyes, the door opened violently. Following a brief fight in the dark, an impact on my head left me unconscious. When I regained awareness, I was in a poorly lit room from which multiple corridors spawned—a labyrinth. Aching and dizzy, I incorporated myself and approached the walls. I then half saw, half sensed with my fingertips, the etchings on the plaster. One reported “I hear the steps coming closer every minute”, whereas another student lamented “Now I can only beg the Salvataur to spare my life”, and a third one regretted “I wish I had asked to review that Algorithmics test’s grading”. The realization of my doom sank in: I fell to my knees, and started sobbing and hitting the writing with my fist, until pain and frustration made me collapse on the floor.

After a few minutes, I stood up and started to explore the labyrinth of the Salvataur: hopelessly, without the knowledge of which room that I entered would be my last…

Input

Input consists of several cases. Each case starts with the number of vertices 3 ≤ V ≤ 10⁴ and edges 3 ≤ E ≤ 5V in the labyrinth’s graph, the number of vertices 3 ≤ R ≤ 1000 in the human’s route, and a real number, the sense of smell 0 ≤ S ≤ 1 of the Salvataur. Next come E pairs u_i v_i, one for each edge of the graph, which is undirected and connected. Finally come R vertices 0 ≤ r_i < V describing the route of the human. Assume that the vertices are numbered from 0, that there are no repeated edges nor edges with u_i = v_i, that r₀ = 0, and that for all 0 < i < R, either r_i−1 = r_i, or there is an edge between r_i−1 and r_i.

At time t = 0, the human is at vertex 0 and the Salvataur at V − 1. For t ≥ 1, they move in turns, starting with the human:

• The human moves from r_i−1 to r_i (or stays at r_i−1, if they are equal). If the Salvataur is at the destination vertex, the human gets caught (and presumably eaten).
• The Salvataur then moves in the following way:
  • If it is in a neighboring vertex to where the human was (r_i−1), it will have smelt him with probability S: in that case, it will move to r_i−1.
  • Otherwise (i.e., if it was not in a neighboring vertex, or if it failed to smell the human), it will move uniformly at random to any of the neighbors of its current vertex. So, it never stays in the same location for two consecutive turns.
  In either case, if it enters the current vertex of the human (r_i), it also captures him.

The input is such that the human has a non-zero probability of surviving after R−2 steps.

Output

For each case, print the probability that the Salvataur catches the human in the last round, given the information that it has not caught the human in any of its preceding moves. That probability must include the human moving to r_R−1 and finding the Salvataur there, and also the Salvataur making its last move to r_R−1. Print the probabilities rounded to a percentage with no decimal figures. The input cases have no precision issues.