#2215. [Poi2011]Conspiracy

题目描述

Byteotia的领土被占领了，国王Byteasar正在打算组织秘密抵抗运动。国王需要选一些人来进行这场运动，而这些人被分为两部分：一部分成为同谋者活动在被占领区域，另一部分是后勤组织在未被占领的领土上运转。但是这里出现了一个问题：

1. 后勤组织里的任意两人都必须是熟人，以促进合作和提高工作效率。 2. 同谋者的团体中任意两人都不能是熟人。 3. 每一部分都至少要有一个人。国王想知道有多少种分配方案满足以上条件，当然也有可能不存在合理方案。现在国王将这个问题交由你来解决！

输入格式

第一行一个整数n（2<=n<=5000）表示有n个人参与该抵抗运动，标号为1..n。 之后有n行，第i行的第一个数ki（0<=ki<=n-1）表示i认识ki个人,随后的ki个数表示i的熟人。 p.s.输入满足：如果i是x的熟人，x会在i的序列中出现同时i也会出现在x的熟人序列中。

输出格式

符合条件的方案总数。

样例

样例输入

4  

2 2 3  

2 1 3  

3 1 2 4  

1 3  

样例输出

3

数据范围与提示

Hint 1和4分到同谋者组织，2和3为后勤组织。 2和4分到同谋者组织，1和3为后勤组织。 4单独分到同谋者组织，1和2、3为后勤组织。