영화 보러 가기

앨런 튜링과 에츠허르 데이크스트라는 영화를 보러 갈 기회가 좀처럼 없다. 두 사람 모두 유럽 사람이라, 영화 관람은 오히려 미국의 문화에 가깝기 때문이다. 그래서 미국을 드물게 방문할 때면, 이들은 주말마다 동료들과 모여 월요일이 될 때까지 큰 화면 앞에서 시간을 보낸다. 극장까지 가는 빠른 길을 찾는 것은 어렵지 않지만, 무엇을 볼지 정하는 일은 쉽지 않다. 서로 취향이 제각각이기 때문이다. 예를 들어 튜링은 로맨스 영화를 무척 좋아하지만, 데이크스트라는 로맨스를 전혀 좋아하지 않는다. 그래서 영화를 고르기가 몹시 어렵다. 그렇다고 각자 흩어져 서로 다른 영화를 볼 수도 없다. 그러면 애초에 함께 모인 의미가 사라지고, 모두가 같은 영화를 본 것이 아니어서 감상을 나눌 수도 없기 때문이다.

이 문제를 해결하기 위해, 이들은 모든 구성원을 만족시키면서 봐야 하는 영화의 수를 최소로 줄이는 방법을 고안했다. 먼저 모두의 취향을 하나의 목록으로 모은다. 이 목록에는 "로맨스", "액션", "공포"와 같은 항목이 들어 있다. 그런 다음 각 영화가 목록의 어떤 취향을 만족시키는지 정한다. 이제 남은 일은 목록에 있는 모든 취향을 만족시키는 가장 작은 영화 집합을 찾는 것이다. 바로 여기서 당신의 도움이 필요하다.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫째 줄에는 두 정수 $M$과 $P$가 주어진다. $M$은 영화의 수, $P$는 취향 목록의 항목 수이며, $1 \le M \le 30$, $1 \le P \le 20$이다. 그다음 $M$개의 줄에는 각 영화가 설명되어 있으며, $i$번째 줄에는 영화 $i$가 만족시키는 취향들이 주어진다. 각 줄에는 $1$개 이상 $P$개 이하의 정수가 있고, 취향은 $1$부터 $P$까지의 번호로 표현된다.

각 데이터 집합마다 "Data Set x:"를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 그다음 줄에는 모두의 취향을 만족시키는 데 필요한 영화의 최소 개수를 출력한다. 모든 취향을 만족시킬 수 없다면 대신 "Impossible"을 출력한다. 연속한 데이터 집합 사이에는 빈 줄을 하나 넣어 구분한다.