Dynamic programming on Trees - Top Level


Given a tree. For each node of the tree is a collection of items that can be placed in the vertex. Each element has a weight - a positive integer. For each edge of the tree defined by the ratio between the peaks, namely, it is known which of the two vertices must be an element with a lower weight. Required to determine the number of different ways to choose the vertices of a tree on the one element that all relations on the edges are respected. Miscellaneous items from the set of one vertex can have the same weight.


The first line contains the number of vertices n (1n1000) in the tree. Followed by n lines, the i-th row is given a list of valid elements in the vertex i. The string begins with an integer k (1k1000) - number of elements. Followed by k integers wj (1wj109) - the weight of elements.

Further, the input data contains n - 1 lines, each of whom recorded two distinct integers a, b (1a, bn), which means that the tree is an edge between vertices a and b, and in the top of a must be placed in an element of lesser weight than the top of b.


Print the number of ways by modulo 1000000007.

Time limit 2 seconds
Memory limit 256 MiB
Input example #1
5 1 2 3 4 5
3 2 3 6
2 3 5
1 2
1 2
1 3
4 2
Output example #1
Author A. Milanin
Source ACM, Ukraine, First Stage, 09.04.2011