题目描述

译自 POI 2011 Round 1. A「Conspiracy」

Bitotia 偷袭了 Byteotia 并占领了很大一块领地。Byteotia 国王 Byteasar 正在被占领的领地内组织人们抵抗运动。国王需要选择一部分人来作为这场运动的核心。他们会被分成两部分：一部分人作为同谋者在领地内指挥，另一部分人作为后勤提供援助。这两部分人需要满足以下条件：

• 后勤组必须两两认识，确保整个组有效率地合作；
• 同谋者必须两两不认识；
• 至少有一个人作为后勤，一个人作为同谋者。

国王希望知道有多少种方案将人们分成两组，以及是否有可能这样分组。

输入格式

第一行一个整数 $n \ (2 \le n \le 5000)$，表示参与抵抗运动的人数。这些人从 $1$ 到 $n$ 编号。

接下来 $n$ 行表示这些人两两认识的情况。第 $i$ 行第一个数 $k_i$ 表示第 $i$ 个人认识的人个数，接下来 $k_i$ 个正整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, k_i}$ 表示第 $i$ 个人认识的人的编号。这些编号以升序输入，且保证 $1 \le a_{i,j} \le n$ 且 $a_{i,j} \neq i$. 保证如果 $x$ 认识 $y$ 则 $y$ 也认识 $x$.

输出格式

输出一行一个整数，表示将人分成同谋者和后勤两组的方案数。如果没有这样的方案，输出 $0$.

样例

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

3

有三种将人们分成两组的方案。同谋者可以是 $1,4$，或 $2,4$，或 $4$ 一个人。