불리언 트리 속이기

이 문제에서는 불리언 트리라고 부를 이진 트리의 한 유형을 다룬다. 이 트리에서는 마지막(가장 깊은) 행을 제외한 모든 행이 완전히 채워져 있으며, 마지막 행의 노드는 가능한 한 왼쪽에 배치된다. 또한 트리의 각 노드는 0개 또는 2개의 자식을 갖는다.

불리언 트리의 특별한 점은 각 노드에 1 또는 0인 불리언 값이 연결되어 있다는 것이다. 또한 각 내부 노드에는 "AND" 게이트 또는 "OR" 게이트가 연결되어 있다. "AND" 게이트 노드의 값은 두 자식의 값에 대한 논리 AND 연산으로 정해진다. 마찬가지로 "OR" 게이트의 값은 두 자식의 값에 대한 논리 OR 연산으로 정해진다. 모든 리프 노드의 값이 입력으로 주어지므로 트리를 따라 위로 올라가며 모든 노드의 값을 계산할 수 있다.

트리의 루트는 특히 중요하다. 루트의 값이 1 또는 0인 V가 되기를 원한다. 하지만 실제 루트의 값은 그렇지 않을 수도 있다. 다행히 속임수를 써서 일부 노드의 게이트 유형을 바꿀 수 있다. AND 게이트를 OR 게이트로 바꾸거나 OR 게이트를 AND 게이트로 바꿀 수 있다.

불리언 트리에 대한 설명과 변경할 수 있는 게이트가 주어질 때, 루트 노드의 값을 V로 만들기 위해 변경해야 하는 게이트의 최소 개수를 구한다. 불가능하다면 "IMPOSSIBLE"을 출력한다(따옴표는 명확성을 위한 것이다).

제한

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

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

2 < M < 30

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

2 < M < 10000

입력 파일의 첫 줄에는 케이스 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 케이스는 M과 V로 시작한다. M은 트리의 노드 수를 나타내며, 모든 노드가 0개 또는 2개의 자식을 갖도록 홀수이다. V는 루트 노드에 원하는 값으로, 0 또는 1이다.

이어서 트리의 각 노드를 설명하는 M개의 줄이 주어진다. $X^{th}$번째 줄은 노드 X를 설명하며, 첫 번째 줄은 노드 1부터 시작한다.

처음 (M−1)/2개의 줄은 내부 노드를 설명한다. 각 줄에는 각각 0 또는 1인 G와 C가 주어진다. G가 1이면 이 노드의 게이트는 AND 게이트이고, 그렇지 않으면 OR 게이트이다. C가 1이면 이 노드의 게이트를 변경할 수 있고, 그렇지 않으면 변경할 수 없다. 내부 노드 X는 노드 2X와 2X+1을 자식으로 갖는다.

다음 (M+1)/2개의 줄은 리프 노드를 설명한다. 각 줄에는 리프 노드의 값인 0 또는 1인 값 I가 하나 주어진다.

이해를 돕기 위해 첫 번째 예제 입력의 트리를 나타낸 그림이 아래에 있다.

각 테스트 케이스에 대해 다음을 출력한다.

Case #X: Y

여기서 X는 테스트 케이스의 번호이고 Y는 루트 노드의 출력값을 V로 만들기 위해 변경해야 하는 게이트의 최소 개수이다. 불가능하다면 "IMPOSSIBLE"을 출력한다(따옴표는 명확성을 위한 것이다).

케이스 1에서는 노드 3의 게이트를 OR 게이트로 바꾸면 루트에서 원하는 결과를 얻을 수 있다. 케이스 2에서는 루트만 변경할 수 있지만, 이를 OR 게이트로 바꾸어도 도움이 되지 않는다.