불 트리 속이기 (작은 입력)

이 문제에서 다루는 이진 트리를 불 트리라고 부른다. 불 트리는 가장 깊은 줄을 뺀 모든 줄이 완전히 채워져 있고, 가장 깊은 줄의 노드는 최대한 왼쪽으로 몰려 있다. 또 모든 노드의 자식 수는 0 또는 2다.

불 트리의 각 노드에는 1 또는 0인 불 값이 하나씩 붙는다. 내부 노드에는 그 밖에 AND 게이트나 OR 게이트가 하나 붙는다. AND 게이트 노드의 값은 두 자식 값의 논리곱이고, OR 게이트 노드의 값은 두 자식 값의 논리합이다. 잎 노드의 값은 모두 입력으로 주어지므로, 트리를 따라 위로 올라가면서 모든 노드의 값을 계산할 수 있다.

우리가 보려는 것은 루트다. 루트의 값이 $V$(0 또는 1)이면 좋겠지만, 실제 루트 값은 그렇지 않을 수 있다. 다행히 우리는 속임수를 써서 일부 노드의 게이트 종류를 바꿀 수 있다. AND 게이트를 OR 게이트로, 또는 OR 게이트를 AND 게이트로 바꾸는 것이다.

불 트리의 구성과 어떤 게이트를 바꿀 수 있는지가 주어질 때, 루트 노드의 값을 $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 게이트이고, 그렇지 않으면 OR 게이트다. $C$가 1이면 이 노드의 게이트를 바꿀 수 있고, 그렇지 않으면 바꿀 수 없다. 내부 노드 $X$의 두 자식은 노드 $2X$와 노드 $2X+1$이다.

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

이해를 돕기 위해, 아래 그림은 첫 번째 예제 입력의 첫 케이스에 해당하는 트리다.

제한

• $1 < N \le 20$
• $2 < M < 30$

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

Case #X: Y

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

첫 번째 예제 입력의 첫 케이스에서는 노드 3의 게이트를 OR로 바꾸면 루트에서 원하는 값을 얻는다.
둘째 케이스에서는 루트만 바꿀 수 있는데, 루트를 OR로 바꿔도 소용이 없다.