Singal Pipes

All submissions for this problem are available.
It is the holi season and Singal has placed c containers on the wall to store colors in. He has numbered them from 1 .. c.
Containers are kept at different heights on the wall and are connected through pipes. A pipe connects 2 containers (at different heights), one at the top end of the pipe and one at the bottom. The container at the bottom end will be filled with color from the container at the top end of pipe.
There are some containers which are at the top (i.e there is no pipe connecting them from the above), Singal fills each of such containers with one of the n colors that he has. Other containers are filled through pipes into them
from above. Liquids of different colors are immiscible, so in case a container is connected to multiple containers from above through pipes, it is filled with the color of any one of them (all the (parent) containers are equally likely to be chosen). Example configuration is given in the figure:
Singal wants to know the number of containers of each color. So he asks your help. For each color b, you have to calculate the expected number of containers of color b.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 Each testcase starts with a line containing 2 integers c and p, the number of containers and pipes respectively. p lines follow, each of the form x y which means there is a pipe with container y at top end and container x at bottom end (x may inherit its color from y). A pipe will occur only once in the input
 Next line contains m and n, number of containers at the top and number of distinct colors that Singal has. m lines follow, each of the form x b, which means that container x has color b. It is guaranteed that each x is distinct and there is no pipe with container x at bottom end.
Output
 For each test case, print a single line containing n values, i^{th} value should be the expected number of containers of color i. Output will be accepted within an error limit of 10^6
Constraints
 1 ≤ T ≤ 100
 1 ≤ c, n ≤ 200
 0 ≤ p ≤ 1000
 1 ≤ x, y ≤ c
 1 ≤ b ≤ n
Example
Input: 1 7 8 1 2 2 5 2 3 3 5 3 6 3 7 4 6 4 7 3 2 5 1 6 2 7 2 Output: 2.666666667 4.333333333
Explanation
The input is the one of the figure, 1 and 2 will have color 1 with probability 0.66667 and 2 with probability 0.33334. 4 with have color 2 with probability 1 and 3 will have color 2 with probability 0.6667 ...
Author:  triveni 
Tags  triveni 
Date Added:  10032015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions