밀크셰이크

당신은 밀크셰이크 가게를 운영한다. 준비할 수 있는 서로 다른 맛은 N가지이며, 각 맛은 "malted" 또는 "unmalted"로 준비할 수 있다. 따라서 2N가지 서로 다른 유형의 밀크셰이크를 만들 수 있다.

각 고객에게는 자신이 좋아하는 밀크셰이크 유형의 집합이 있으며, 그중 적어도 하나의 유형을 준비해 두면 만족한다. 고객이 좋아하는 유형 중 "malted" 맛은 최대 하나이다.

다음 조건을 만족하도록 N개의 밀크셰이크 배치를 만들려고 한다:

• 각 밀크셰이크 맛마다 정확히 하나의 배치가 있으며, 그 배치는 맥아 첨가이거나 맥아 무첨가이다.

• 각 고객에 대해, 그 고객이 좋아하는 밀크셰이크 유형을 적어도 하나 만든다.

• 맥아 첨가 배치의 수가 가능한 한 최소이다.

이러한 제약 조건에서 모든 고객을 만족시킬 수 있는지, 가능하다면 어떤 유형의 밀크셰이크를 만들어야 하는지 구하라.

모든 고객을 만족시키는 것이 가능하다면, 맥아 첨가 배치의 수를 최소화하는 답은 단 하나뿐이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

C = 100 1 ≤ N ≤ 10 1 ≤ M ≤ 100

큰 데이터 세트 (테스트 세트 2 - 비공개)

C = 5 1 ≤ N ≤ 2000 1 ≤ M ≤ 2000

한 테스트 케이스에서 모든 고객의 T 값의 합은 3000을 초과하지 않는다.

입력 파일의 테스트 케이스 수를 나타내는 정수 C가 한 줄에 주어진다. 각 테스트 케이스마다 다음이 주어진다:

• 밀크셰이크 맛의 수를 나타내는 정수 N이 한 줄에 주어진다.

• 고객 수를 나타내는 정수 M이 한 줄에 주어진다.

• 각 고객마다 하나씩 M개의 줄이 주어지며, 각 줄에는 다음이 포함된다:

• 고객이 좋아하는 밀크셰이크 유형의 수를 나타내는 정수 T ≥ 1 뒤에

• 고객이 좋아하는 각 유형마다 하나씩 T개의 정수 쌍 "X Y"이 주어진다. 여기서 X는 1 이상 N 이하인 밀크셰이크 맛이고, Y는 맥아 무첨가를 나타내는 0 또는 맥아 첨가를 나타내는 1이다. 다음에 유의하라:

• 한 고객에 대해 같은 쌍이 두 번 이상 등장하지 않는다.

• 각 고객에게는 자신이 좋아하는 맛이 적어도 하나 있다 (T ≥ 1).

• 각 고객은 맥아 첨가 맛을 최대 하나만 좋아한다. (각 고객에 대해 Y = 1인 쌍은 최대 하나이다.)

이 모든 수는 공백 하나로 구분된다.

입력 파일에 등장하는 순서대로 각 테스트 케이스마다 하나씩 C개의 줄을 출력한다. 각 줄에는 테스트 케이스 번호 X가 1부터 시작하는 문자열 "Case #X: "을 출력한 뒤, 다음 중 하나를 출력한다:

• 고객의 선호를 만족시킬 수 없다면 문자열 "IMPOSSIBLE"; OR

• 1부터 N까지 각 맛마다 하나씩, 공백으로 구분된 N개의 정수. 해당 맛을 맥아 무첨가로 준비해야 하면 0, 맥아 첨가로 준비해야 하면 1이다.

첫 번째 케이스에서는 첫 번째 고객을 만족시키기 위해 맛 #1을 맥아 첨가로 만들어야 한다. 나머지 모든 맛은 맥아 무첨가로 만들 수 있다. 두 번째 고객은 맛 #2을 맥아 무첨가로 받으면 만족하고, 세 번째 고객은 맛 #5을 맥아 무첨가로 받으면 만족한다.

두 번째 케이스에는 맛이 하나뿐이다. 고객 중 한 명은 그 맛을 맥아 첨가로 원하고 다른 한 명은 맥아 무첨가로 원한다. 두 고객을 모두 만족시킬 수는 없다.