가짜 뉴스 만들기

소셜 네트워크에 사람 $n$명이 있고 1번부터 $n$번까지 번호가 붙어 있다. 뉴스 하나는 실수 $d$개 $c_1, c_2, \dots, c_d$로 나타내고, $c_j$는 그 뉴스가 $j$번 주제를 밀어붙이는 정도다. 이 값은 정수가 아니어도 된다.

$i$번 사람에게는 관심 벡터 $a_{i1}, a_{i2}, \dots, a_{id}$와 기준값 $t_i$가 주어진다. $i$번 사람은 $a_{i1}c_1 + a_{i2}c_2 + \dots + a_{id}c_d = t_i$일 때만 그 뉴스를 마음에 들어 한다. 합이 기준값보다 크든 작든, 정확히 같지 않으면 마음에 들어 하지 않는다.

뉴스를 받은 사람은 그 뉴스를 마음에 들어 하면 자기 공유 목록에 적힌 사람 모두에게 그대로 보낸다. 마음에 들어 하지 않으면 아무에게도 보내지 않는다. 뉴스를 처음 받을 사람은 직접 고르고, 여러 명을 골라도 된다. 다만 뿌리는 뉴스는 모두 같은 뉴스 하나여야 한다.

$n$명 전원이 마음에 들어 하는 뉴스 하나를 설계하려고 한다. 그런 뉴스가 없는 경우도 있고, 그때는 없다고 보고한다. 있으면 전원에게 뉴스가 도달하도록 하는 데 필요한 최초 배포 인원의 최솟값을 구한다.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 데이터 집합이 $K$개 주어진다.

각 데이터 집합의 첫 줄에는 사람 수 $n$과 주제 수 $d$가 주어진다. 이어지는 $n$개 줄 중 $i$번째 줄에는 정수 $a_{i1}, \dots, a_{id}$, 기준값 $t_i$, 공유 목록의 크기 $k_i$, $i$번 사람이 뉴스를 보내는 사람의 번호 $k_i$개가 순서대로 주어진다.

$1 \le K \le 20$, $1 \le n \le 100$, $1 \le d \le 20$, $|a_{ij}| \le 100$, $|t_i| \le 1000$, $0 \le k_i \le n - 1$이다. 공유 목록에 적힌 번호는 서로 다르고 $i$ 자신은 들어 있지 않다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 1부터 시작하는 데이터 집합 번호다. 다음 줄에는 전원이 마음에 들어 하는 뉴스가 있으면 전원에게 뉴스가 도달하도록 하는 데 필요한 최초 배포 인원의 최솟값을, 없으면 Impossible을 출력한다. 각 데이터 집합의 출력 뒤에 빈 줄을 하나 출력한다.