시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 42 32 28 73.684%

문제

비록 ALPS 회원들이 까다로울지라도 그들은 피자를 좋아한다. 그들은 음료수와 함께 T(<=20)개의 다른 토핑이 얹을 수 있는 '피자의땅'에 주문을 했다.

그 토핑을 간단히 1부터 T까지 숫자로 매겨져 있다. 그러므로 소들은 숫자들을 주문한다. 너의 일은 몇몇 학생들이 다양한 토핑 조합에 대해 관용을 베풀지 않을 때 얼마나 많은 종류의 피자를 만들 수 있는가를 알아내는 것이다. (ex. 몇몇 학생들은 간단하게 피망을 먹지 않거나 버섯을 먹지 않는다.) 

N (1 <= N <= 52)은 가능한 모든 토핑 조합(토핑이 하나도 없는 피자도 가능하다)으로 만들 수 있는 피자를 제한하는 개수이다. 각각의 제한은 1..T 사이의 숫자들의 세트로 되어있다. 그리고 이것은 몇몇 만들 수 있는 가능한 피자를 제외시킨다.

"5 3"과 같은 제한은 어떠한 피자도 토핑 #5와 #3을 함께 포함할 수는 없다. 이것은 예를 들어 3,5,6 토핑을 얹은 피자는 제외된다는 뜻이다.

입력

첫 번째 줄에 두 개의 공백을 두고 T와 N이 들어온다.

2..N+1줄까지 각각의 줄에 공백으로 구분된 숫자들이 들어오는데 첫 번째 숫자 Z (1 <= Z <= T)는 제한된 토핑의 개수를 의미하고, 이어서 Z개의 토핑 숫자가 들어온다.

출력

토핑들의 조합으로 만들 수 있는 모든 가능한 피자의 개수를 출력한다.

예제 입력

6 5
1 1
2 4 2
3 3 2 6
1 5
3 3 4 6

예제 출력

10

힌트

출처

  • 문제를 번역한 사람: author6