스택 관리

처음에 각각 C장의 앞면이 보이는 카드가 놓인 N개의 스택으로 솔리테어 게임을 한다. 각 카드에는 값과 무늬가 있으며, 게임에서 값과 무늬의 조합이 같은 두 카드는 없다.

한 번의 이동으로 다음 중 하나를 할 수 있다.

• 서로 다른 스택의 맨 위에 같은 무늬의 카드가 둘 이상 있으면, 그 카드들 중 값이 가장 작은 카드 하나를 게임에서 제거할 수 있다. (스택에서 마지막 카드를 제거해도 스택 자체는 그대로 남으며, 단지 빈 스택이 된다.)

• 빈 스택이 있으면, 비어 있지 않은 임의의 스택 하나에서 맨 위의 카드를 가져와 그 빈 스택의 맨 위에 놓을 수 있다. 즉, 그 스택의 유일한 카드로 놓을 수 있다.

일련의 이동을 통해 최종적으로 각 스택에 최대 한 장의 카드만 남게 할 수 있으면 게임에서 승리한다. 시작 배치가 주어질 때, 게임에서 승리할 수 있는지 판별한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 2 ≤ P ≤ 60000. 모든 i에 대해 0 ≤ $P_{i}$ < P이다. $P_{i}$번째 미리 만들어진 스택에는 정확히 C장의 카드가 있다. 한 테스트 케이스에서 값과 무늬의 조합이 같은 두 카드는 없다.

소규모 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ N ≤ 4. 모든 i에 대해 2 ≤ $C_{i}$ ≤ 13. 2 ≤ C ≤ 13. 모든 i와 j에 대해 1 ≤ $V_{ij}$ ≤ 13. 모든 i와 j에 대해 1 ≤ $S_{ij}$ ≤ 4.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ N ≤ 50000. 모든 i에 대해 2 ≤ $C_{i}$ ≤ 50000. 2 ≤ C ≤ 50000. 4 ≤ N × C ≤ $10^{5}$. 모든 i와 j에 대해 1 ≤ $V_{ij}$ ≤ 50000. 모든 i와 j에 대해 1 ≤ $S_{ij}$ ≤ 50000.

입력의 첫 번째 줄에는 테스트 케이스에서 사용할 미리 만들어진 스택의 수 P가 주어진다. 이어서 P개의 줄이 주어진다. 이 중 i번째 줄은 i번째 미리 만들어진 스택의 카드 수를 나타내는 정수 $C_{i}$로 시작하고, 뒤이어 순서가 있는 정수 쌍 $C_{i}$개가 주어진다. 이 정수 쌍 중 j번째 쌍에는 정수 $V_{ij}$와 $S_{ij}$가 있으며, 각각 i번째 미리 만들어진 스택에서 위로부터 j번째 카드의 값과 무늬를 나타낸다.

그다음 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 정수 N과 C가 있는 한 줄로 시작하며, 각각 스택 수와 각 스택의 카드 수를 나타낸다. 그다음 줄에는 테스트 케이스에 사용할 미리 만들어진 스택의 인덱스(0부터 시작)를 나타내는 N개의 정수 $P_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 게임에서 승리할 수 있으면 POSSIBLE, 그렇지 않으면 IMPOSSIBLE이다.

예제 케이스 #1에는 각각 카드가 두 장씩 있는 두 개의 스택이 있다. 첫 번째 스택은 맨 위에 무늬가 2인 7가 있고, 그 아래에 무늬가 1인 7가 있다. 두 번째 스택은 맨 위에 무늬가 2인 3가 있고, 그 아래에 무늬가 2인 6가 있다.

다음과 같이 게임에서 승리할 수 있다.

• 두 번째 스택에서 무늬가 2인 3를 제거한다.

• 두 번째 스택에서 무늬가 2인 6를 제거한다. 그러면 두 번째 스택이 빈다.

• 무늬가 2인 7를 두 번째 스택으로 옮긴다. 그러면 모든 스택에 최대 한 장의 카드만 있으므로 승리 조건이 충족된다.

예제 케이스 #2에는 각각 카드가 두 장씩 있는 세 개의 스택이 있다. 이 경우에는 게임에서 승리할 수 없다. 가능한 유일한 이동은 세 번째 스택의 맨 위에 있는 무늬가 4인 5를 제거하는 것이며, 이 이동으로는 새로운 이동이 가능해지지 않는다.