밀크셰이크 (라지)

밀크셰이크 가게를 운영한다. 만들 수 있는 맛은 $N$가지이고, 각 맛은 몰트를 넣어서 준비하거나 넣지 않고 준비한다. 그래서 밀크셰이크 종류는 모두 $2N$가지다.

손님마다 좋아하는 종류의 집합이 정해져 있다. 그 집합에 속한 종류를 하나라도 준비하면 그 손님은 만족한다. 한 손님이 좋아하는 종류 가운데 몰트를 넣은 것은 많아야 하나다.

다음 조건을 지키면서 $N$개의 배치를 만든다.

• 맛마다 배치를 정확히 하나 만들고, 그 배치는 몰트를 넣은 것이거나 넣지 않은 것이다.
• 모든 손님이 자기가 좋아하는 종류를 적어도 하나 받는다.
• 몰트를 넣은 배치의 개수가 가능한 한 적다.

모든 손님을 만족시킬 수 있는지 판정하고, 가능하면 어떤 종류를 준비해야 하는지 구한다. 만족시킬 수 있다면 몰트를 넣은 배치 수를 최소로 하는 준비 방법은 하나뿐이다.

첫 줄에 테스트 케이스의 개수 $C$가 주어진다. 각 테스트 케이스는 다음 형식으로 주어진다.

• 첫 줄에 맛의 개수 $N$
• 다음 줄에 손님 수 $M$
• 이어지는 $M$개의 줄에 손님 정보가 한 줄에 하나씩 주어진다. 각 줄은 그 손님이 좋아하는 종류의 개수 $T$로 시작하고, 그 뒤에 종류를 나타내는 정수 쌍 "$X$ $Y$"가 $T$개 이어진다. $X$는 $1$부터 $N$까지의 맛 번호이고, $Y$는 몰트를 넣지 않은 종류면 $0$, 넣은 종류면 $1$이다.

한 줄에 있는 수는 공백 하나로 구분된다.

제한

• $1 \le C \le 5$
• $1 \le N \le 2000$
• $1 \le M \le 2000$
• $T \ge 1$이고, 한 손님 안에서 같은 쌍이 두 번 나오지 않는다
• 한 손님이 좋아하는 종류 가운데 몰트를 넣은 것은 많아야 하나다 ($Y = 1$인 쌍이 많아야 하나)
• 한 테스트 케이스에 있는 모든 손님의 $T$ 합은 $3000$을 넘지 않는다

입력에 주어진 순서대로 테스트 케이스마다 한 줄씩, 모두 $C$줄을 출력한다. $X$번째 줄은 Case #X: 로 시작하고, 그 뒤에 다음 중 하나를 쓴다.

• 모든 손님을 만족시킬 수 없으면 IMPOSSIBLE
• 만족시킬 수 있으면 맛 $1$번부터 $N$번까지에 해당하는 정수 $N$개를 공백으로 구분해 쓴다. 몰트를 넣지 않고 준비하는 맛은 $0$, 넣어서 준비하는 맛은 $1$이다.

첫 번째 예제의 첫째 테스트 케이스에서는 첫 손님 때문에 1번 맛에 몰트를 넣어야 한다. 나머지 맛은 모두 몰트 없이 준비하면 된다. 둘째 손님은 몰트 없는 2번 맛으로, 셋째 손님은 몰트 없는 5번 맛으로 만족한다.

둘째 테스트 케이스에서는 맛이 하나뿐인데 한 손님은 몰트를 넣은 것을 원하고 다른 손님은 넣지 않은 것을 원한다. 그래서 두 손님을 함께 만족시킬 수 없다.