밀크셰이크 (Small)

밀크셰이크 가게를 운영한다. 준비할 수 있는 맛은 $N$가지이고, 맛마다 몰트를 넣은 것과 넣지 않은 것을 만들 수 있다. 따라서 만들 수 있는 밀크셰이크 종류는 모두 $2N$가지다.

손님마다 좋아하는 밀크셰이크 종류의 집합이 정해져 있고, 그중 하나라도 준비해 두면 그 손님은 만족한다. 한 손님이 좋아하는 종류 중 몰트를 넣은 것은 많아도 하나다.

다음 조건을 모두 만족하도록 밀크셰이크를 $N$통 만들려고 한다.

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

모든 손님을 만족시킬 수 있는지 판정하고, 가능하면 어떤 종류를 만들어야 하는지 구하라.

모든 손님을 만족시킬 수 있는 경우, 몰트를 넣은 통의 수를 최소로 하는 답은 하나뿐이다.

첫째 줄에 테스트 케이스의 수 $C$가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 밀크셰이크 맛의 수 $N$이 주어진다.
• 둘째 줄에 손님의 수 $M$이 주어진다.
• 이어지는 $M$개의 줄에 손님 한 명의 정보가 각각 주어진다. 각 줄은 그 손님이 좋아하는 종류의 개수 $T$로 시작하고, 그 뒤에 정수 쌍 $X\ Y$가 $T$개 온다. $X$는 맛 번호로 $1$ 이상 $N$ 이하이고, $Y$는 몰트를 넣지 않은 것이면 $0$, 넣은 것이면 $1$이다.

같은 줄의 수는 모두 공백 하나로 구분된다.

제한

• $1 \le C \le 100$
• $1 \le N \le 10$
• $1 \le M \le 100$
• $T \ge 1$
• 한 손님의 정보에서 같은 쌍 $(X, Y)$는 두 번 나오지 않는다.
• 한 손님이 좋아하는 종류 중 $Y = 1$인 쌍은 많아도 하나다.

테스트 케이스마다 한 줄씩, 입력에 주어진 순서대로 $C$개의 줄을 출력한다. 각 줄은 Case #X: 로 시작한다. 여기서 $X$는 $1$부터 시작하는 테스트 케이스 번호다. 그 뒤에 이어서 다음을 출력한다.

• 손님의 취향을 모두 만족시킬 수 없으면 IMPOSSIBLE을 출력한다.
• 만족시킬 수 있으면 $1$번 맛부터 $N$번 맛까지에 대응하는 정수 $N$개를 공백으로 구분해 출력한다. 그 맛을 몰트 없이 준비해야 하면 $0$, 몰트를 넣어 준비해야 하면 $1$이다.

첫 번째 예제의 첫째 테스트 케이스에서는 첫 손님을 만족시키려고 $1$번 맛에 몰트를 넣어야 한다. 나머지 맛은 모두 몰트를 넣지 않아도 된다. 둘째 손님은 몰트를 넣지 않은 $2$번 맛으로, 셋째 손님은 몰트를 넣지 않은 $5$번 맛으로 만족한다.

둘째 테스트 케이스에는 맛이 하나뿐이다. 한 손님은 몰트를 넣은 것을 좋아하고 다른 손님은 넣지 않은 것을 좋아하므로, 두 손님을 함께 만족시킬 수 없다.