SP14946 SANTA2 - Travelling Santa

At last, Santa is on his way! He's got a number of presents to deliver to various households, and he won't stop until he's disposed of them all. However, each present is only suitable for one gender - for example, men might enjoy such things as baseball bats, football helmets, and certain adult reading material, while women would prefer make-up, knitting needles, and certain other adult reading material. At the moment, Santa is in a neighbourhood with $ H $ ( $ 1 \leq H \leq 50 $ ) houses (numbered $ 1..H $ ), connected by $ R $ ( $ 1 \leq R \leq 10^{4} $ ) roads. The family living in house $ i $ includes $ M_i $ ( $ 0 \leq M_i \leq 10 $ ) males and $ F_i $ ( $ 0 \leq F_i \leq 10 $ ) females. The $ i $ th road runs between distinct houses $ A_i $ and $ B_i $ , and can be travelled in either direction. No pair of houses is directly connected by more than one road. Santa starts at house $ 1 $ , carrying $ M_S $ ( $ 0 \leq M_S \leq 50 $ ) male-appropriate and $ F_S $ ( $ 0 \leq F_S \leq 50 $ ) female-appropriate presents. He then repeats the following process until he's out of gifts. First, he moves randomly to an adjacent house (a house reachable by taking one road) - it's guaranteed that there will be at least one such house. If he currently has $ m $ male-appropriate and $ f $ female-approrpiate presents, his probability of moving to adjacent house $ i $ is proportional to the value of $ M_i m + F_i f $ . Of course, the probabilities for all adjacent houses must add up to $ 1 $ . Note that if this value is $ 0 $ for all adjacent houses, then Santa will move to any of them with equal probability. After reaching the new house, he delivers a male present to it with probability $ \frac{m}{m+f} $ , and a female present otherwise. Wanting to plan ahead to leaving this neighbourhood, Santa is curious as to where he'll end up. He'd like you to calculate the probability of him being at each of the $ H $ houses when he runs out of presents.

First line: $ H $ and $ R $ Next $ H $ lines: $ M_i $ and $ F_i $ , for $ i = 1..H $ Next $ R $ lines: $ A_i $ and $ B_i $ , for $ i = 1..R $ Next line: $ M_S $ and $ F_S $

$ H $ lines: The probability of Santa finishing his present-delivering process at house $ i $ , rounded off to 6 decimal places, for $ i = 1..H $