A6323 | $「POI2011 R1」同谋者 Conspiracy$

时间限制3s

内存限制256MB

通过 / 提交0/0

题目描述

**译自 POI 2011 Round 1. A「[Conspiracy](https://szkopul.edu.pl/problemset/problem/-Q4lH1UCWU8G3YE94ez0AK30/site/?key=statement)」** 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$.

输入 #1

输出 #1

C++ 编辑器

输入

输出