#Z6026. 关灯问题

    ID: 1150 Type: Default 1000ms 256MiB Tried: 1 Accepted: 0 Difficulty: 10 Uploaded By: Tags>动态规划其他位运算

关灯问题

题目描述

有 n 盏灯,编号 0n10 \sim n - 1 ,有 m 个开关,第 i 盏开关管 cic_i 盏灯,分别是 ai,1,ai,2,...,ai,cia_{i, 1}, a_{i, 2}, ..., a_{i, c_i} 。 刚开始所有灯都是开着的,问最少需要多少次按开关的操作才能把所有灯关上。

输入格式

第1行包含两个整数 n(n<20)n(n<20)m(m<100)m(m<100),分别表示灯的数量和开关数量。

第2~m+1行,每行先输入一个整数cic_i,表示第 i 盏开关管 cic_i 盏灯,接下来输入cic_i个整数,表示控制灯的编号。

输出格式

输出一个整数表示答案,无解输出-1.

样例输入 #1

3 3
2 0 1
2 1 2
1 1

样例输出 #1

3

Statistics

Related

In following contests:

20240122C_day3