Tom and game

Tom love to play games with Tony.

They think a orderly tetrad (t,i,j,k) is valid, when it satisfy,

1. $1\leq i,j,k\leq t$

2. Exist a positive integer s, which can divide both i and j, and is not smaller than k.

They prepare some tetrads, take turns to operate. When one can't operate, he loses. A valid operate is,

1. Choose a tetrad.

2. Change it to another valid tetrad which is smaller than it on dictionary order.

When compare two tetrads, compare the first element. If equal, compare the second element, and so on.

They think that prepare tetrads every time they want to play is troublesome. So they paint a tree, there is a tetrad on each point. When they want to play, Tom random choose a point P, Tony random choose a point Q. Then they copy down tetrads on points which are on the route connect P and Q (include P and Q), start the game.

Tom always operate first, he wants to know the probability of he wins.

Multi test cases(about 8). For each case, the first line contains a positive integer n, indicates the number of points in the tree. In the next n-1 lines, each line contains two integers i and j, indicates there is an edge connect point i and point j. In the next n lines, the i-th line contains four integers, a、b、c、d, indicates the orderly tetrad on point i is (a,b,c,d).

$1\leq n\leq 10000;1\leq i,j\leq n;1\leq a,b,c,d\leq 10000$

It's assured that the tetrad on each point is valid.

For each case, output a fraction "x/y", indicates the probability of Tom wins, x and y should be co-prime. If Tom is bound to fail, output "0/1".

2
1 2
1 1 1 1
2 1 2 1
5
1 2
2 3
3 4
4 5
1 1 1 1
2 1 1 1
2 1 2 1
2 2 1 1
1 1 1 1

3/4
3/5

BestCoder Round #40