Recently, Yuta designed and published a doomsday survival game.

The background of the game is a small town. There are n houses and several undirected roads connecting between them. As the game progresses, some zombies will appear in some houses, and they can walk to other houses through the roads. To survival from the zombies, players can build fences on the roads or even destroy some roads (But the map must be connected, i.e., for each pair of houses (i,j), there must be at least one path from i to j during the game).

Now Rikka is playing this game. To give her a better experience, Yuta tells her there will be m zombies, the ith zombie will appear at the a_ith house, and it can walk through the fences with height less than h_i units.

Using this information, Rikka finishes her defense measures: she destroys as many roads as possible, and there are only n-1 roads now(The map is still connected). On each of the remaining roads, Rikka builds a fence on it. Since the game has some kind of randomness, the height of the fence on the ith road is randomly selected from all integers in [l_i,r_i] with equal probability.

A house is safe if and only if no zombie can reach this house. Now Rikka wants to calculate the probability of existing at least one safe houses.

The first line contains a single integer t(1 ≤ t ≤ 5), the number of the testcases.

For each testcase, the first line contains two integers n,m(1 ≤ n,m ≤ 2000), the number of the houses and the zombies.

Then n-1 lines follow, each line contains four integers ui,vi,li,ri(1 ≤ u ≠ v ≤ n, 1 ≤ li ≤ ri ≤ 109), describes a road and the fence on it.

Then m lines follow, each line contains two integers ai,hi(1 ≤ ai ≤ n, 1 ≤ hi ≤ 109), describes a zombie.

For each testcase, if the answer's simplest fraction representation is , you need to output .

2
4 2
1 2 1 2
2 3 1 2
1 4 1 2
1 2
3 2
5 2
1 2 1 10
2 3 2 9
1 4 3 12
2 5 4 6
1 7
5 5

374341633
888437475