Competitions

# Tree

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.

#### Input

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.

#### Output

Print the number of ways by modulo 1000000007.

Time limit 2 seconds
Memory limit 256 MiB
Input example #1
4
5 1 2 3 4 5
3 2 3 6
2 3 5
1 2
1 2
1 3
4 2

Output example #1
10

Author A. Milanin
Source ACM, Ukraine, First Stage, 09.04.2011