题目描述

有一颗N个节点的树，节点用1,2,....,N编号。你要给它染色，使得相邻节点的颜色不同。有M种颜色，用1,2,.....,M编号。每个节点可以染M种颜色中的若干种，求不同染色方案的数量除以(10^9 + 7)的余数。

输入格式：

第1 行，2 个整数N,M。
接下来N行，第i行表示节点i可以染的颜色。第1个整数k_i，表示可以染的颜色数量。接下来ki个整数，表示可以染的颜色编号。
最后N - 1行，每行2个整数A_i,B_i，表示边(A_i,B_i)。

输出格式：

1 个整数，表示所有的数。

输入样例#1：

2 2
1 1
2 1 2
1 2

输出样例#1：

1

数据范围：

• 对于30% 的数据，1≤N≤10;1≤M≤4；

• 对于60% 的数据，1≤N≤200;1≤M≤200；

• 对于100% 的数据，1≤N≤5000;1≤M≤5000。