描述

  X_{1},X_{2},...,X_{n}n人去射箭,现在要从n​个靶子(Y_{1},...,Y_{n})中为他们选择合适他们的靶子,每个人对应一个靶子,不多不少。已知每个人讨厌的靶子,李华想知道一共有多少种选靶方案。(即求二分图匹配为N的方案数)

输入格式

  第一行一个正整数n,表示有n人。

  接下来n行,第i行描述X_{i}​的信息,第一个非负整数s,表示X_{i}讨厌的靶子数量,接下来有s个数字Z_{1},...Z_{s},表示X_{i}​讨厌靶子Y_{i\in Z}。数字之间由空格隔开。

输出格式

  输出仅有一行,为所有满足条件的选靶方案数。

样例输入

4
1 2
2 2 3
2 3 4
1 4

样例输出

4

样例解释

  可行的方案如下:

  ①​X_{1}\to Y_{1},X_{2}\to Y_{4},X_{3}\to Y_{2},X_{4}\to Y_{3}

  ②X_{1}\to Y_{3},X_{2}\to Y_{4},X_{3}\to Y_{1},X_{4}\to Y_{2}

  ③X_{1}\to Y_{3},X_{2}\to Y_{4},X_{3}\to Y_{2},X_{4}\to Y_{1}

  ④X_{1}\to Y_{4},X_{2}\to Y_{1},X_{3}\to Y_{2},X_{4}\to Y_{3}

数据范围与约定

  对于100%的数据:n\leq 100,所有人讨厌的靶子数之和不大于25​。

注释

  这TM真的是概率专练?