D - Pre-match Party Invitation
問題文
Aliceの大学では紅白対抗の大会があります。この大会には紅白それぞれ $N + M$ 人の選手が参加します。ここで、人 $1, 2, \cdots, N$ は紅組の選手、人 $N + 1, N + 2, \cdots, N + M$ は白組の選手です。Aliceはこの大会の運営を務めています。
彼女は大会に先立って、交流会を開催しようと思います。この交流会は参加させたい選手に招待状を送り、招待状を受け取った選手のみが参加することができます。また、招待状には招待状を送った人の「名簿」も添付されます。
人 $i$ には自分の所属する組とは異なる組に $k_i$ 人の「嫌いな人」がいて、「嫌いな人」が $1$ 人でも招待されている場合、交流会には参加しないことが分かっています。より厳密には、人 $i$ の選手は次の条件を満たすとき、招待状を受け取っても交流会には参加しません。
- 条件 : 人 $a_{i,1}, a_{i,2}, \cdots, a_{i,k_i}$ のうち $1$ 人以上が「名簿」に記載されている。
- ここで、 $1 \le i \le N$ ならば $0 \le k_i \le M$、 $N + 1 \le a_{i,j} \le N + M$ であることが、 $N + 1 \le i \le N + M$ ならば $0 \le k_i \le N$、 $1 \le a_{i,j} \le N$ であることが（すなわち、紅組の選手が嫌いな人は白組の選手であり、白組の選手が嫌いな人は紅組の選手であることが）保証される。
Aliceは大会の運営として、なるべく多くの選手を交流会に参加させたいです。Aliceが上手く選手たちに招待状を送ることで、最大何人の選手が参加する可能性がありますか？
制約
Final (70点)
- $1 \le N, M \le 150$
- $1 \le i \le N$ ならば $0 \le k_i \le M$、 $N + 1 \le a_{i,j} \le N + M$
- $N + 1 \le i \le N + M$ ならば $0 \le k_i \le N$、 $1 \le a_{i,j} \le N$
- $p \ne q$ ならば $a_{ip} \ne a_{iq}$
- 入力はすべて整数である。
Hard (5点)
- Finalの制約に以下の制約を追加
- $1 \le M \le 16$
Normal (25点)
- Finalの制約に以下の制約を追加
- $1 \le M \le 16$
- $N + 1 \le i \le N + M$ ならば $k_i = 0$
Easy (90点)
- Finalの制約に以下の制約を追加
- $1 \le N, M \le 8$
- $N + 1 \le i \le N + M$ ならば $k_i = 0$
Beginning (10点)
- Finalの制約に以下の制約を追加
- $N = 1$
- $1 \le M \le 8$
- $N + 1 \le i \le N + M$ ならば $k_i = 0$
入力
$N\ \ M$
$k_1\ \ a_{1,1}\ \ a_{1,2}\ \ \cdots\ \ a_{1,k_1}$
$k_2\ \ a_{2,1}\ \ a_{2,2}\ \ \cdots\ \ a_{2,k_2}$
$\ \vdots$
$k_{N+M}\ \ a_{N+M,1}\ \ a_{N+M,2}\ \ \cdots\ \ a_{N+M,k_{N+M}}$
出力
参加する可能性がある最大の人数を出力し、最後に改行してください。
1 4
2 2 3
0
0
0
0
4
人 $2,3,4,5$ を招待すると $4$ 人の選手を参加させることができます。
人 $1$ は人 $2$ と人 $3$ が嫌いなため、人 $2$ あるいは人 $3$ を招待すると、人 $1$ を招待しても参加しないことに注意してください。
入力例1はBeginning, Easy, Normal, Hard, Finalの制約を満たします。
5 11
6 14 11 7 16 6 10
5 13 11 10 8 14
1 11
4 9 8 7 13
8 11 6 15 16 12 10 14 7
0
0
0
0
0
0
0
0
0
0
0
11
入力例2はNormal, Hard, Finalの制約を満たします。
15 8
1 20
3 19 23 20
1 21
7 20 18 16 23 22 17 19
0
7 22 21 18 20 16 17 23
6 16 18 22 19 23 17
7 21 16 20 18 23 19 22
2 18 17
4 21 17 23 20
3 18 19 22
7 22 19 16 23 20 21 17
6 18 17 23 20 21 19
6 22 23 20 17 21 16
8 19 21 22 18 23 20 17 16
5 9 7 4 8 15
2 7 4
5 14 8 4 15 1
3 3 8 4
5 11 13 3 14 4
1 15
4 6 4 9 15
1 14
15
入力例3はHard, Finalの制約を満たします。