Do you remember your childhood? You played many meaningless games. If you don’t remember, you can look at any kid and instead of thinking “how can he play such a horrible boring game?”, think “Did I used to play like this as well?”. Watching the kids playing, you noticed one thing — those games are endless. For example, they keep throwing balls without any specific goal, in beach they build sand houses restlessly, or they may be cooking in their small kitchen-ware endlessly throughout the day. You could not tolerate all these meaningless endless games, rather you decided to give them some educational game! You just came to a beach and drew N circles on the sand, connected all the circles with N − 1 lines so that if any kid start from any circle and follow the connecting lines he can end up at any other circle. That means, if we consider the circles as vertices and connecting lines as edges the graph will be a tree in graph theoretic term. You also attached two numbers with each circle. Suppose for the i-th circle the numbers are Li and Hi (Li ≤ Hi). Kids love marbles so in each circle you put Hi marbles. The marbles are colorful. In a circle all the marbles will be of the same color and any two marbles of the same color will always be in the same circle. So any two marbles belonging to the same circle are considered indistinguishable and two marbles from different circles are always distinguishable. Now the game starts: you will call a boy and describe him the rules. He can start from a circle, follow some connecting lines (may be none) and end up in a circle (may be same). However, the kid is not interested to go back through the same line he used coming into the circle he is in. In graph theoretic term such sequence of circles/connecting lines are called simple path. While going through the i-th circle he can take any number of marbles between Li and Hi. He only collects marble from a circle if that circle is part of his path. Now after walking through the path and collecting marbles, his task is to divide these collected marbles into maximum number of groups so that same colored marbles appear same number of times in all the groups. Every collected marbles should belong to exactly one group. The kid will mark this maximum number in a paper. Let’s name this entire round as traversal. The kid is clever and will never do the same traversal twice. That is, either the path will be different or the number of marbles taken from a particular circle will differ. Please note, path from circlei to circlej will be considered same as a path from circlej to circlei. As you can imagine if there are many circles and the difference of the numbers Li and Hi is big then this game is kind of endless but educative! We are interested in the number of traversals that will yield the maximum number of groups to be g. For example, suppose the graph contains two circles A (1, 2) and B (2, 2). The first number in the parenthesis is Li and the second number is Hi for the corresponding circles. Let’s assume they are connected with a line. Here a kid can make 5 different traversals. All these traversals are recorded in the following table. The circle name is given in the parenthesis. Simple path A A A-B A-B B Chosen Numbers [1(A)] [2(A)] [1(A), 2(B)] [2(A), 2(B)] [2(B)] Maximum number of groups 1 2 1 2 2 So 1 group appears 2 times, 2 groups appear 3 times.
2/2 Input The first line of the input contains T (T ≤ 50), number of test cases. Hence T cases follow. Each case starts with a positive integer N (N ≤ 10000), number of circles in this case. Hence following N − 1 lines describe the connecting lines. Each line will contain two integers u and v (1 ≤ u, v ≤ N ), denoting which pair of circles is connected by this connecting line. You can assume that the connecting lines will form a valid tree. Then there will be 2 more lines of input for the case. First line will contain the L values and the second line will contain the corresponding H (1 ≤ L ≤ H ≤ 50) values. That is, i-th L or H corresponds to the i-th circle. Output For each case in the first line output: ‘Case C:’ where C is the case number (starting from 1). Then 50 lines will follow. g-th of these lines (1 ≤ g ≤ 50) will be of the format: ‘g: ans’ where ans is the number of different traversals having g as the answer. Since the ans may be big, please output modulo 21092013. Since a circle will contain at most 50 marbles, so it is not possible to make more than 50 groups in a traversal. Please note, output for the sample input is truncated. Sample Input 2 2 12 12 22 5 12 23 34 45 44444 44444 Sample Output Case 1: 1: 2 2: 3 ... 48 more lines with answer 0... Case 2: 1: 0 2: 0 3: 0 4: 15 ... 46 more lines with answer 0...