hackercupai/hackercup huggingface dataset:
You're playing a video game that features **N** different areas, numbered from
1 to **N**. There are **M** one-way paths that each connect two areas. The
**i**th path runs from area **Ai** to a different area **Bi**. No pair of
paths directly connect the same pair of areas, and for every area it's
impossible to start at that area and follow a non-empty sequence of paths to
return to that area. In other words, the game's layout is a directed acyclic
graph.

You start in area 1. **K** other distinct areas each contain an item to
collect — the **i**th of these is area **Ii**. As soon as you've visited these
**K** areas at least once each, you win! You'd like to do so as fast as
possible.

At any point in time, if there are no outgoing paths leading away from your
current area, you automatically respawn in area 1 after a delay of **R**
seconds. Otherwise, you get to choose one such path and attempt to follow it.
Unfortunately, this game relies entirely on Random Number Generation to
determine whether or not you'll be successful, regardless of your skill. In
particular, with probability **P**, you'll successfully travel along your
chosen path for **D** seconds, ending up in a new area. On the other hand,
with probability 1 - **P**, you'll instead perish and respawn in area 1 after
a delay of **R** seconds.

What's the minimum expected time for you to collect all **K** items, given
that you play optimally? This is guaranteed to be possible — that is, all
**K** areas that contain items are reachable from area 1. Your output should
have at most 10-6 absolute or relative error.

### Input

Input begins with an integer **T**, the number of times you play the game. For
each time, there is first a line containing the space-separated integers
**N**, **M**, and **K**. The second line contains the space-separated integers
**D** and **R**. The third line contains the real value **P** which is given
with at most 4 decimal places. The fourth line contains the **K** space-
separated integers **I1** to **IK**. Then, **M** lines follow, the **i**th of
which contains the space-separated integers **Ai** and **Bi**.

### Output

For the **i**th time you play the game, print a line containing "Case #**i**:
" followed by the expected time it will take you to collect all of the items
if you play optimally.

### Constraints

1 ≤ **T** ≤ 50
2 ≤ **N** ≤ 100,000
1 ≤ **M** ≤ 100,000
1 ≤ **K** ≤ min(20, **N** \- 1)
0.5 ≤ **P** ≤ 1.0
1 ≤ **D**, **R** ≤ 1,000
1 ≤ **Ai**, **Bi** ≤ **N**
2 ≤ **Ii** ≤ **N**

The answer for each game is guaranteed to be less than 1030.

### Explanation of Sample

In the first game, it takes you 10 seconds to reach the only item, and then
you win. There's no chance of failure. The second game is the same as the
first, but now you fail to reach the item with probability 0.5. On average you
will fail once before reaching the item, so you'll incur an average penalty of
3 seconds on top of the 10 seconds it takes you to succeed, for a total of 13
seconds.