题目描述

有一颗$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

提示

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

• 对于60% 的数据，$1 \le N \le 200; 1 \le M \le 200$；

• 对于100% 的数据，$1 \le N \le 5000; 1 \le M \le 5000$。