Cheating a Boolean Tree (Small)

This problem uses a kind of binary tree we call a boolean tree. In a boolean tree every row is completely filled except possibly the deepest row, and the nodes in the deepest row are as far to the left as possible. Every node has either 0 or 2 children.

Each node of a boolean tree carries a boolean value, 1 or 0. Each interior node also carries either an AND gate or an OR gate. The value of an AND gate node is the logical AND of its two children's values, and the value of an OR gate node is the logical OR of its two children's values. The values of all leaf nodes are given in the input, so the value of every node can be computed by working up the tree.

The root is what we care about. We would like the root to have the value $V$, either 1 or 0, but that may not be the value it actually has. Luckily we can cheat and change the gate type of some nodes: an AND gate becomes an OR gate, or an OR gate becomes an AND gate.

Given a description of a boolean tree and of which gates can be changed, find the minimum number of gates that have to be changed to make the value of the root node $V$. If this is impossible, output IMPOSSIBLE.

The first line contains the number of test cases, $N$. $N$ test cases follow.

The first line of each test case contains $M$ and $V$. $M$ is the number of nodes in the tree, and it is odd so that every node has 0 or 2 children. $V$ is the desired value of the root node, 0 or 1.

Then $M$ lines follow describing each of the tree's nodes. The $X$th line describes node $X$, starting with node 1 on the first line.

The first $(M-1)/2$ lines describe the interior nodes. Each line contains $G$ and $C$, each being either 0 or 1. If $G$ is 1 then the gate for this node is an AND gate, otherwise it is an OR gate. If $C$ is 1 then the gate for this node can be changed, otherwise it cannot. Interior node $X$ has nodes $2X$ and $2X+1$ as its children.

The next $(M+1)/2$ lines describe the leaf nodes. Each line contains one value $I$, 0 or 1, the value of the leaf node.

The picture below shows the tree of the first case of the first example input.

Limits

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

For each test case, output one line in the form

Case #X: Y

where $X$ is the test case number and $Y$ is the minimum number of gates that must be changed to make the value of the root node $V$. If that cannot be done, output IMPOSSIBLE in place of $Y$.

In the first case of the first example input, changing the gate of node 3 to an OR gate gives the desired value at the root.
In the second case only the root can be changed, and changing it to an OR gate does not help.