#2751 크리스마스 전구

1 s   128 MB  

Description

어린이들에게 가장 좋아하는 휴일을 물어보면 대부분 크리스마스를 꼽을 것이다.
 
크리스마스가 되면 산타 할아버지가 밤중에 몰래 오셔서 아이들에게 선물을 주고 가시기 때문이다.
 
물론 나이가 들면 산타 할아버지의 정체를 알게되고, 더 이상 선물도 받을 수 없겠지만 그 전까지는 일년 중 가장 특별한 날이라는 것에는 대부분 공감할 것이다.
 
산타 할아버지가 선물을 넣을 양말을 트리에 걸어 놓고 기대에 부풀어 자는 그 기분이란.
 
아직까지 산타 할아버지의 존재를 믿고 있는 윤호는 이번에도 크리스마스 선물을 받을 수 있었다.
 
저번까지는 색연필이나 스케치북 따위를 받아서 많이 섭섭했는데, 올해는 꼬마 전구 회로 키트를 받아서 기분이 매우 좋다고 한다.
 
이 회로 키트에는 서로 다른 색을 내는 N개의 꼬마 전구와 그 전구를 켜고 끌 수 있는 M개의 스위치가 들어있는데, 이 스위치는 연결된 전구에 불이 꺼져 있을 경우 켜고 불이 켜져 있는 경우에는 다시 끄는 기능이 있다. 즉, 자신에게 연결된 전구의 상태를 바꾸는 셈이다.
 
그런데 산타 할아버지가 준비한 선물에 루돌프도 관심이 있었는지 윤호가 받기 전에 전구와 스위치 몇 개를 들고 도망을 가버렸다.
 
꼬마 전구야 학교 과학실에서 훔쳐오면 되기에 상관 없었지만, 키트에 맞춰 제작한 스위치를 구할 곳이 없어서 결국 자동차 공장에서 사용하는 공업용 스위치를 대신 사용하기로 했다. 문제는 이 스위치가 자동차에 들어갈 목적으로 만들어져서 원래 것보다 훨씬 강한 전류를 흘려 보낸다는 점이다.
 
그래서 키트에 있는 스위치와는 달리 두 개 이상의 공업용 스위치가 같은 전구에 전류를 흘려 보낼 경우 전구가 이를 견디지 못하고 폭발하게 된다.
 
물론 일반 스위치와는 아무 문제 없이 작동을 한다. 다행히도 윤호는 같이 동봉된 설명서를 읽었기 때문에 이 사실을 알고 있다.
 
이제 윤호는 이 스위치를 적절히 이용해서 여러 가지 조합으로 전구를 키고 싶어한다.
 
이것저것 막 켜보면서 원하는 형태가 나올 때 까지 시도를 해볼 수도 있지만, 실수로 공업용 스위치 2개를 한 전구에 켜서 전구가 폭발하거나 자주 껏다가 다시 켜는 과정에서 전구의 수명이 빨리 단축되 는 것을 원하지 않는 윤호는 여러분에게 이 작업을 맡겼다.
 
윤호가 올해 크리스마스를 행복하게 보낼 수 있도록 도와주자!

Input

첫 줄에 전구의 개수 N(1 ≤ N ≤ 20)과 스위치의 개수 M(1 ≤ M ≤ 20)이 주어진다.
 
두 번째 줄부터 각 줄마다 스위치의 정보가 M개의 줄에 걸쳐 주어진다.
 
먼저 스위치의 종류(A는 일반 스위치, B는 공업용 스위치)와 스위치에 연결된 전구의 개수 B N(1 ≤ B ≤ N)가 주어지고,
그뒤로 B개의 전구의 번호가 오름차순으로 주어진다. 전구의 번호는 1~N이며, 한 개의 스위치가 같은 전구에 중복되게 연결된 경우는 없다.
 
다음 줄에 윤호가 만들고 싶은 조합의 수 Q(1 ≤ Q ≤ 10,000)가 주어진다. 이후 Q줄에 걸쳐서 각줄에 윤호가 만들고자 하는
조합에서 켜지는 전구의 수 Ci가 주어지고 그 뒤로 켜져 있어야하는 전구의 번호가 오름차순으로 주어진다.
 
여기에서도 전구의 번호가 중복되지는 않는다.

Output

각 Q개의 조합에 대하여 해당 조합의 전구를 키기 위해 작동시켜야 하는 최소의 스위치의 개
 
수를 각 줄에 출력한다. 만약 주어진 스위치로 윤호가 원하는 조합을 만드는 것이 불가능할 경
 
우  -1을 출력한다. 전구가 폭발하는 조합은 무효임에 유의하라.

Sample Input

Sample Output

4 4
A 1 1
A 2 1 2
A 3 1 2 4
B 1 3
6
1 1
1 2
1 3
2 1 3
3 1 2 3
3 1 3 4
1
2
1
2
2
4

HINT

첫 번째 조합은 1번 스위치 하나로 만들 수 있다.
 
두 번째 조합은 1, 2번 스위치를 작동시킬 경우 1번 전구가 꺼지기 때문에 만들 수 있다.
 
세 번째 조합은 4번 스위치 하나로 만들 수 있다.
 
네 번째 조합은 1, 4번 스위치로 만들 수 있다.
 
다섯 번째 조합은 2, 4번 스위치로 만들 수 있다.
 
여섯 번째 조합은 4개의 스위치를 모두 작동시키면 만들 수 있다.

Source

shake! 2016 예선