Description

There is a tree with $N$ nodes, numbered $1, 2, \cdots, N$. You need to color it so that adjacent nodes have different colors. There are $M$ colors, numbered $1, 2, \cdots, M$. Each node may be colored with a subset of the $M$ colors. Compute the number of different valid colorings modulo $10^9 + 7$.

Input Format

The first line contains two integers $N, M$.

Then follow $N$ lines. The $i$-th line describes the colors allowed for node $i$: the first integer $k_i$ is the number of allowed colors, followed by $k_i$ integers giving the allowed color indices.

Finally, the last $N - 1$ lines each contain two integers $A_i, B_i$, indicating an edge $(A_i, B_i)$.

Output Format

Output one integer, the number of valid colorings modulo $10^9 + 7$.

2 2
1 1
2 1 2
1 2

1

Hint

• For 30% of the testdata, $1 \le N \le 10; 1 \le M \le 4$.

• For 60% of the testdata, $1 \le N \le 200; 1 \le M \le 200$.

• For 100% of the testdata, $1 \le N \le 5000; 1 \le M \le 5000$.

Translated by ChatGPT 5