Luffy and Zoro are good friends, and are on their course to seek the One-Piece Treasure. However they got separated during their voyage, so Zoro, not knowing where Luffy is, decided to go straight for the treasure anyway. He managed to travel very close to where the treasure is:

"The Forest of Luck".

There is one small problem. Zoro is completely ignorant in recognizing roads and directions, so he is not able to pass the forest with ease.

He is currently located at the entrance, while the treasure itself is also located in the forest somewhere.

The forest can be seen as a rooted tree graph. That is, it consists of some intersections and roads such that, between each pair of intersections there is exactly one way to travel from one point to another without traversing a
road twice. The entrance can be viewed as the root, so that a parent-child relation could be deduced for each pair of adjacent vertices.

At each intersection there is a mysterious device called "the Lucky Spin Machine". For an intersection V_i, if it has C_i children, then there will be exactly C_i balls in the machine. On each ball, a direction is indicated. It points to some child intersection U_i of the intersection V_i. Each child of V_i are written on exactly one ball. When Zoro spins the machine, a ball (if still available) will drop by random, then Zoro will follow the direction on ball (i.e. walk to the intersection written on the ball). Each ball in a
device, however, has different probability to drop, which will be given in the input data.

Note that a ball that is dropped is never put back to the machine. And the drop rates are given as relative probability. So let's say that initially there are three balls in a machine, with drop rate 1:2:3, then if the ball
with drop rate 2 is dropped from a spin, the remaining two ball will drop with probability 1/4 and 3/4. The drop rate of a ball will never be 0.

So one can imagine that Zoro starts at the entrance, spins the machine at the entrance and getting a ball, then follows the ball's instruction to the next intersection. And at the intersection he'd spin again, getting another ball, traveling to his next intersection and so on. He will continue doing this until he get to the treasure.
At some point he might reach a leaf, or he might spin out all the available balls at some intersection, in which case he will simply retreat back to the previous intersection (i.e. parent). One should be able to see that eventually
Zoro would arrive at the treasure. When that happens, Zoro will be happy and he would stop his long journey.

You might ask, if the ball that dropped is not necessarily pointing to the correct direction, what's the point of following it anyway?

Well, do remember that Zoro is a completely idiot when it comes to recognizing roads. So he decides that if he follow the instruction on the balls, he would at least arrive at the destination someday!! Otherwise he might travel some
same roads over and over again (without even knowing) and be lost forever!

Anyway, there are a total of N intersections(be numbered 1 ~ N).
Zoro is currently at intersection 1, and the treasure is at intersection N. Given the map information and the information of the balls in each device, please decide for Zoro, how long is expected for him to arrive at the treasure?