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.
- 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.
- For each test case, print a single line containing n values, ith value should be the expected number of containers of color i. Output will be accepted within an error limit of 10^-6
- 1 ≤ T ≤ 100
- 1 ≤ c, n ≤ 200
- 0 ≤ p ≤ 1000
- 1 ≤ x, y ≤ c
- 1 ≤ b ≤ n
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
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 ...
|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|
Fetching successful submissions