题目描述

农民约翰逊的公牛队非常喜欢打篮球。但他们都不想和其他公牛一起打篮球,因为他们相信其他人都非常弱。农民约翰逊有N头牛(我们从$1$到$N$的奶牛数)和M谷仓(我们从$1$到$M$的谷仓),这是他的公牛的篮球场。然而,他的公牛都非常蹩脚,他们只喜欢在一些特定的谷仓里玩,不想和其他人分享谷仓。

所以农民约翰逊很难安排他的公牛,他希望你帮助他。当然,找到一个解决方案很容易,但你的任务是找到有多少解决方案。

你应该知道,解决方案是每头公牛都可以在他喜欢的谷仓里打篮球,没有两只公牛共用谷仓。

为了使问题变得容易,假设解决方案的数量不会超过1000000。

输入

在第一行输入中包含两个整数$N$和$M$ $(1 <= N <= 20,1 <= M <= 20)$。然后是$N$线。$i-th$行首先包含一个整数$P(1 <= P <= M)$,指的是我喜欢玩的谷仓牛的数量。然后遵循 $P$ 整数,它给出 $P$ 谷仓的数。

输出

在一行中打印单个整数,这是解决方案的数量。 输入数 1

3 4
2 1 4
2 1 3
2 2 4

输出数位 1

4

来源

POJ 月刊