Norela
시간 제한1초메모리 제한512 MB
최대 24개의 주문이 각각 지정한 카드 집합을 뒤집을 때, 모든 카드가 앞면이 되도록 사용할 주문의 최소 개수와 사전순으로 가장 작은 번호 목록을 구한다.
문제
Adrian 3세는 마법사 왕자다. 세계 마법사의 날(11월 4일)에 그는 꿈에 그리던 여인 Norela의 마음을 사로잡고 싶었다. 그에게는 n장의 카드가 있고, 처음에는 모두 뒷면이 위로 가게 탁자에 놓여 있다. Adrian은 m개의 주문을 쓸 수 있으며, 주문은 q a1 a2 … aq 형식이다. 주문을 사용하면 a1 a2 … aq번째 카드가 순서대로 뒤집힌다. (a1 a2 … aq는 모두 서로 다르다.) 카드는 뒷면이면 앞면이 되고 앞면이면 뒷면이 되며, 모든 주문은 많아야 한 번씩만 사용할 수 있다. 라이벌 Manea Long Eyebrow보다 먼저 Norela의 마음을 사로잡도록 Adrian을 도와주자!
n장의 카드를 모두 앞면으로 만들기 위해 사용해야 하는 주문의 최소 개수를 구하고, 사용한 주문의 번호도 알아내자. 답이 여러 개라면 사전순으로 가장 작은 답을 출력한다.
입력
첫째 줄에 두 정수 n과 m이 주어진다.
다음 m개 줄에는 각 주문의 설명 q a1 a2 … aq가 주어지며, q는 그 주문으로 뒤집히는 카드의 수, a1 a2 … aq는 그 카드들의 번호다.
출력
첫째 줄에는 사용한 주문의 최소 개수를 나타내는 정수 하나를 출력하고, 둘째 줄에는 그 주문들의 번호를 출력한다. 사용한 주문의 개수가 최소인 답이 여러 개라면 사전순으로 가장 작은 답을 출력한다.
제한
- n ≤ 60
- m ≤ 24
힌트
정수 집합 a1 a2 … an이 다른 집합 b1 b2 … bn보다 사전순으로 작다는 것은, 1과 n 사이의 어떤 k에 대해 a1=b1, a2=b2, ..., ak-1 = bk-1이고 ak < bk인 경우를 말한다.