7194 : 전구 스위치
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N개의 전구와 M개의 스위치가 주어집니다. 각 스위치마다 제어할 수 있는 전구들의 목록이 정해져 있습니다. 스위치를 누르면 제어되는 전구들의 상태가 반전됩니다. 모든 전구를 켜기 위해 작동해야 하는 최소 스위치 조작 횟수를 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 전구의 개수 N과 스위치의 개수 M이 주어집니다. (1 ≤ N, M ≤ 20)
둘째 줄에 전구의 초기 상태(0: 꺼짐, 1: 켜짐)가 주어집니다.
셋째 줄부터 M개의 줄에 걸쳐 각 스위치가 제어하는 전구들의 인덱스(1-indexed) 목록이 주어집니다.
둘째 줄에 전구의 초기 상태(0: 꺼짐, 1: 켜짐)가 주어집니다.
셋째 줄부터 M개의 줄에 걸쳐 각 스위치가 제어하는 전구들의 인덱스(1-indexed) 목록이 주어집니다.
출력 설명
모든 전구를 켜는 최소 조작 횟수를 출력합니다. 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2
0 0 0
1 2
2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1도움
이 스위치 구성으로는 모든 전구를 동시에 켤 수 없습니다.