[POI2011] KON-Conspiracy

## 描述 Byteotia的领土被占领了，国王Byteasar正在打算组织秘密抵抗运动。国王需要选一些人来进行这场运动，而这些人被分为两部分：一部分成为同谋者活动在被占领区域，另一部分是后勤组织在未被占领的领土上运转。但是这里出现了一个问题： 1. 后勤组织里的任意两人都必须是熟人，以促进合作和提高工作效率。 2. 同谋者的团体中任意两人都不能是熟人。 3. 每一部分都至少要有一个人。国王想知道有多少种分配方案满足以上条件，当然也有可能不存在合理方案。 现在国王将这个问题交由你来解决！ ## 输入 第一行一个整数n（2<=n<=5000）表示有n个人参与该抵抗运动，标号为1..n。 之后有n行，第i行的第一个数ki（0<=ki<=n-1）表示i认识ki个人,随后的ki个数表示i的熟人。 输入满足如果i是x的熟人，x会在i的序列中出现同时i也会出现在x的熟人序列中。 ## 输出 符合条件的方案总数。

Hostile Bitotia launched a sneak attack on Byteotia and occupied a significant part of its territory. The King of Byteotia, Byteasar, intends to organise resistance movement in the occupied area. Byteasar naturally started with selecting the people who will form the skeleton of the movement. They are to be partitioned into two groups: the conspirators who will operate directly in the occupied territory, and the support group that will operate inside free Byteotia. There is however one issue - the partition has to satisfy the following conditions: Every pair of people from the support group have to know each other - this will make the whole group cooperative and efficient. The conspirators must not know each other. None of the groups may be empty, i.e., there has to be at least one conspirator and at least one person in the support group. Byteasar wonders how many ways there are of partitioning selected people into the two groups. And most of all, whether such partition is possible at all. As he has absolutely no idea how to approach this problem, he asks you for help.

The first line of the standard input holds one integer $n$ ($2\le n\le 5000$), denoting the number of people engaged in forming the resistance movement. These people are numbered from 1 to $n$ (for the sake of conspiracy!). The $n$ lines that follow describe who knows who in the group. The $i$-th of these lines describes the acquaintances of the person $i$ with a sequence of integers separated by single spaces. The first of those numbers, $k_i$ ($0\le k_i\le n-1$), denotes the number of acquaintances of the person $i$. Next in the line there are $k_i$ integers $a_{i,1},a_{i,2},\cdots,a_{i,k_i}$ - the numbers of $i$'s acquaintances.The numbers $a_{i,j}$ are given in increasing order and satisfy $1\le a_{i,j}\le n$,$a_{i,j}\ne i$. You may assume that if $x$ occurs in the sequence $a_i$ (i.e., among $i$'s acquaintances), then also $i$ occurs in the sequence $a_x$(i.e., among $x$'s acquaintances).

In the first and only line of the standard output your program should print out one integer: the number of ways to partition selected people into the conspirators and the support group. If there is no partition satisfying aforementioned conditions, then 0 is obviously the right answer.

4
2 2 3
2 1 3
3 1 2 4
1 3

3