소들의 피자
시간 제한2초메모리 제한128 MB
최대 20가지 토핑 중에서 주어진 제약 집합을 모두 포함하지 않는 부분집합의 개수를 세는 문제입니다.
문제
소들은 피자를 좋아하고, 다양한 토핑 조합도 즐긴다. 피자 가게에는 토핑이 T개 있으며, 토핑 번호는 1부터 T까지이다.
일부 토핑 조합은 소들이 먹지 못하는 조합이다. 제약 하나는 함께 들어 있으면 안 되는 토핑 번호들의 집합으로 주어진다. 어떤 피자에 한 제약의 모든 토핑이 포함되어 있으면 그 피자는 가능한 피자로 세지 않는다.
토핑을 하나도 고르지 않는 경우를 포함해, 만들 수 있는 토핑 조합의 수를 구하라.
입력
- 첫째 줄에 두 정수
T와N이 공백으로 구분되어 주어진다.1 <= T <= 20,1 <= N <= 52이다. - 다음
N개의 줄에는 제약이 하나씩 주어진다. 각 줄의 첫 번째 정수는 제약에 포함된 토핑 수Z이다.1 <= Z <= T이다. - 이어지는
Z개의 정수는 함께 포함되면 피자가 불가능해지는 토핑 번호들이다. 한 제약 안의 토핑 번호는 모두 서로 다르다.
출력
- 만들 수 있는 가능한 피자 토핑 조합의 수를 나타내는 정수 하나를 출력한다.