레이팅 미적용설명
전체 집합은 \(\{0, 1, \dots, U-1\}\)이다. 이 집합의 부분집합 \(M\)개가 주어진다. 합집합이 전체 집합이 되도록 하는 최소 개수의 부분집합을 고르시오. 그 최소 개수를 출력하고, 전체를 덮을 수 없으면 \(-1\)을 출력한다.
제약
입력 형식
첫 줄에 \(U\)와 \(M\)이 주어진다 (\(1 \le U \le 16\), \(1 \le M \le 16\)). 이어지는 \(M\)개의 줄은 각각 하나의 부분집합을 나타내며, 정수 \(k\) 다음에 \([0, U-1]\) 범위의 서로 다른 원소 \(k\)개가 주어진다.
출력 형식
필요한 최소 부분집합 개수를 출력하고, 불가능하면 \(-1\)을 출력한다.
예제 1
입력
3 3
2 0 1
2 1 2
1 2
출력
2
예제 2
입력
3 2
1 0
1 1
출력
-1
예제 3
입력
4 3
2 0 1
2 2 3
1 0
출력
2
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그