불 트리 속이기

불 트리는 이진 트리의 한 종류다. 이 트리는 1번부터 $M$번까지 번호가 붙은 홀수 개의 노드로 이루어진다. 1번부터 $(M-1)/2$번까지는 내부 노드이고, $i$번 노드는 $2i$번 노드와 $2i+1$번 노드를 자식으로 갖는다. $(M+1)/2$번부터 $M$번까지는 리프 노드다.

노드의 값은 다음과 같이 정해진다. 리프 노드는 0 또는 1의 값을 갖는다. 내부 노드는 AND 게이트이거나 OR 게이트다. 아래 그림이 불 트리의 예다.

서브트리의 값도 자연스럽게 정의된다. 서브트리의 루트가 리프 노드라면 그 리프 노드의 값이 서브트리의 값이다. 서브트리의 루트가 내부 노드라면 그 노드의 게이트로 왼쪽 서브트리의 값과 오른쪽 서브트리의 값을 결합한 결과가 서브트리의 값이다. 예를 들어 위 그림에서 2번 노드를 루트로 하는 서브트리의 값은 다음과 같다.

Val[2] = Val[4] AND Val[5] = (Val[8] OR Val[9]) AND 1 = (0 OR 1) AND 1 = 1

우리는 전체 트리의 값, 즉 Val[1]이 $V$가 되기를 원한다. $V$는 입력으로 주어지는 0 또는 1이다. 지금 트리의 값이 $V$와 다를 수 있으므로 내부 노드 몇 개의 게이트를 바꾸는 것이 허용된다. 즉 AND 게이트를 OR 게이트로, OR 게이트를 AND 게이트로 바꿀 수 있다. 위 그림에서 파란색으로 표시된 노드가 바꿀 수 있는 노드다.

불 트리와 바꿀 수 있는 내부 노드가 주어질 때, 전체 트리의 값을 $V$로 만들기 위해 바꿔야 하는 게이트의 최소 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스는 다음과 같이 구성된다.

• 첫 줄에 $M$과 $V$가 주어진다. $M$은 불 트리의 노드 개수이고 홀수다. $V$는 전체 트리의 값으로 만들고 싶은 값이다. ($1 \le M \le 10000$, $V$는 0 또는 1)
• 다음 $(M-1)/2$개의 줄에는 내부 노드의 정보 $a_i$와 $b_i$가 1번 노드부터 차례로 주어진다. $a_i$는 그 노드의 게이트를 뜻하며 0은 OR 게이트, 1은 AND 게이트다. $b_i$는 그 노드의 게이트를 바꿀 수 있는지를 뜻하며 1이면 바꿀 수 있고 0이면 바꿀 수 없다.
• 다음 $(M+1)/2$개의 줄에는 리프 노드의 값 $a_i$가 $(M+1)/2$번 노드부터 차례로 주어진다.

각 테스트 케이스마다 Case #c: x 형식으로 한 줄에 답을 출력한다. $c$는 1부터 매기는 테스트 케이스 번호다. $x$는 전체 트리의 값을 $V$로 만들기 위해 바꿔야 하는 게이트의 최소 개수다. 게이트를 어떻게 바꿔도 전체 트리의 값을 $V$로 만들 수 없다면 $x$ 자리에 IMPOSSIBLE을 출력한다.