3290 - 染色计数
时间限制 : 2 秒
内存限制 : 128 MB
有一颗N个节点的树，节点用1,2,\cdots,N编号。你要给它染色，使得相邻节点的颜色不同。有M种颜色，用1,2,\cdots,M编号。每个节点可以染M种颜色中的若干种，求不同染色方案的数量除以(10^9 + 7)的余数。
输入
第1 行，2 个整数N,M。
接下来N行，第i行表示节点i可以染的颜色。第1个整数k_i，表示可以染的颜色数量。接下来k_i个整数，表示可以染的颜色编号。
最后N - 1行，每行2个整数A_i,B_i，表示边(A_i,B_i)。
输出
1 个整数，表示所有的数。
样例
输入
2 2 1 1 2 1 2 1 2
输出
1
提示
• 对于100% 的数据，1 \le N \le 4000; 1 \le M \le 4000。
来源
用户上传