불 트리 속이기 (큰 입력)

불 트리는 다음 두 조건을 만족하는 이진 트리다.

• 가장 깊은 층을 뺀 모든 층이 노드로 꽉 차 있고, 가장 깊은 층의 노드는 최대한 왼쪽으로 몰려 있다.
• 모든 노드의 자식 수가 0개 또는 2개다.

불 트리의 각 노드에는 0 또는 1의 불 값이 붙는다. 자식이 둘인 내부 노드에는 AND 게이트나 OR 게이트가 하나씩 붙는다. AND 게이트가 붙은 노드의 값은 두 자식 값의 논리곱이고, OR 게이트가 붙은 노드의 값은 두 자식 값의 논리합이다. 리프 노드의 값은 입력으로 주어지므로 아래에서 위로 올라가며 모든 노드의 값이 정해진다.

관심 대상은 루트다. 루트가 원하는 값 V를 가지면 좋겠지만, 실제 값이 다를 수 있다. 대신 일부 노드의 게이트 종류를 바꿀 수 있다. AND 게이트를 OR 게이트로 바꾸거나 OR 게이트를 AND 게이트로 바꾸는 것이다. 바꿀 수 있는 노드는 입력에서 지정된 노드뿐이다.

불 트리의 모양과 값, 그리고 어떤 게이트를 바꿀 수 있는지가 주어진다. 루트의 값을 V로 만들려면 게이트를 최소 몇 개 바꿔야 하는지 구한다. 어떻게 바꿔도 루트를 V로 만들 수 없으면 IMPOSSIBLE을 출력한다.

첫 줄에 테스트 케이스의 개수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 M과 V가 주어진다. M은 트리의 노드 수이고, 모든 노드의 자식 수가 0개 또는 2개가 되도록 항상 홀수다. V는 루트가 가져야 하는 값으로 0 또는 1이다.

이어지는 M개의 줄은 트리의 노드를 하나씩 설명한다. $X$번째 줄이 노드 $X$를 설명하고, 첫 줄이 노드 1이다.

앞의 $(M-1)/2$개 줄은 내부 노드를 설명한다. 각 줄에는 G와 C가 주어지며 둘 다 0 또는 1이다. G가 1이면 이 노드의 게이트는 AND 게이트이고, 0이면 OR 게이트다. C가 1이면 이 노드의 게이트를 바꿀 수 있고, 0이면 바꿀 수 없다. 내부 노드 $X$의 두 자식은 노드 $2X$와 노드 $2X+1$이다.

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

첫 번째 예제의 1번 테스트 케이스에 주어진 트리를 그림으로 나타내면 다음과 같다.

제한

• $2 \le N \le 20$
• $3 \le M \le 9999$, M은 홀수

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: Y

X는 테스트 케이스의 번호이고, Y는 루트의 값을 V로 만들기 위해 바꿔야 하는 게이트의 최소 개수다. 루트를 V로 만들 수 없으면 Y 자리에 IMPOSSIBLE을 출력한다.

첫 번째 예제의 1번 테스트 케이스에서는 노드 3의 게이트를 OR 게이트로 바꾸면 루트가 원하는 값을 가진다.

2번 테스트 케이스에서는 루트만 바꿀 수 있는데, 루트를 OR 게이트로 바꿔도 루트의 값은 그대로다.