Ciel and Random Walk

Problem code: CIELWALK

All submissions for this problem are available.

Today, Ciel's restaurant is closed. Ciel is bored, so she decides to take a walk randomly.

This town has N intersections and M one way roads. The i-th road connects from the Ai-th intersection to the Bi-th intersection. Ciel is in the 1st intersection now, and Ciel's house is in the N-th intersection.

If Ciel is in the i-th intersection, she will take a walk as follows:

  • If i = N, her walk is ended.
  • Otherwise, she chooses an integer k such that Ak = i uniformly randomly, she walks along the k-th road.

On the way, S intersections have beautiful flowers. Let the F1-th intersection, the F2-th intersection, ..., and the FS-th intersection have beautiful flowers. Can you tell the probability that Ciel last sees the flowers in the Fi-th intersection? That is to say, can you tell the probability that she visits the Fi-th intersection, then she goes to N-th intersection without visiting other intersections having beautiful flowers?

Input

The first line contains 3 integers N, M and S. Then, next line has S integers F1, F2, ..., FS. Next M lines have 2 integers each, Ai and Bi.

Output

An output should contain S lines. In the i-th line, print the probability that Ciel last sees beautiful flowers at the Fi-th intersection. These values must have an absolute error no more than 10-6.

Constraints

1 ? S < N ? 30
1 ? F1 < F2 < ... < FS < N
Ai ? Bi
If i ? j and Ai = Aj, then Bi ? Bj
For each 1 ? i < N, Ciel can go from the i-th intersection to the N-th intersection, directly or indirectly.

Sample Input 1

4 6 3
1 2 3
1 2
2 1
1 3
3 1
2 4
3 4

Sample Output 1

0
0.5
0.5

Sample Input 2

4 6 1
2
1 2
2 1
1 3
3 1
2 4
3 4

Sample Output 2

0.6666666666667

Sample Input 3

2 1 1
1
1 2

Sample Output 3

1

Notes

The sum of output values can be less than 1, because Ciel may go back to her house without seeing beautiful flowers.

Author: laycurse
Date Added: 24-11-2011
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

What is the constraint for M?

subscriber @ 18 Dec 2011 10:24 PM
What is the constraint for M?

@subscriber M is not limited.

hiroto_adm @ 18 Dec 2011 10:33 PM
@subscriber M is not limited.

explanation of the second

karaggeorge @ 18 Dec 2011 11:03 PM
explanation of the second example?? how can it be 2/3....

@karaggeorge Please think

hiroto_adm @ 18 Dec 2011 11:05 PM
@karaggeorge Please think yourself about it

@karaggeorge Please think

hiroto_adm @ 18 Dec 2011 11:06 PM
@karaggeorge Please think yourself about it

Are you sure that at tests

kunyavskiy @ 18 Dec 2011 11:14 PM
Are you sure that at tests vertex there is a way to vertex N from every vertex?

@kunyavskiy Please read

hiroto_adm @ 18 Dec 2011 11:20 PM
@kunyavskiy Please read Constraints

i have checked it over and

karaggeorge @ 18 Dec 2011 11:21 PM
i have checked it over and over again... i believe the correct answer is 3/4 or 0.75 there are 4 ways to go from 1 to 4 : 1. 1->2->4 2. 1->2->1->3->4 3. 1->3->4 4. 1->3->1->2->4 but only 3 of them (1,2,4) contain 2 as the last flowered intersection, so 3/4 what am i getting wrong ?

@karaggeorge Please read the

hiroto_adm @ 18 Dec 2011 11:26 PM
@karaggeorge Please read the problem statement carefully and think again

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions