Cheating a Boolean Tree (Large)

A boolean tree is a binary tree with these two properties.

• Every level except the deepest one is completely filled, and the nodes on the deepest level sit 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, 0 or 1. Each interior node also carries one gate, either AND or OR. The value of a node with an AND gate is the logical AND of its two children's values, and the value of a node with an OR gate is the logical OR of its two children's values. The values of the leaf nodes are given in the input, so the values of all nodes follow from the bottom up.

The root is what matters here. You would like the root to hold the desired value V, but its actual value may differ. Instead you can change the gate on some nodes: an AND gate becomes an OR gate, or an OR gate becomes an AND gate. Only the nodes marked in the input can be changed.

Given the shape and values of a boolean tree together with the list of gates that can be changed, find the minimum number of gates you must change to make the root hold V. If no set of changes makes the root hold V, print 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 is always odd, so every node has 0 or 2 children. V is the value the root must hold, 0 or 1.

The next M lines describe the nodes of the tree, one per line. Line $X$ describes node $X$, and the first line describes node 1.

The first $(M-1)/2$ of those lines describe the interior nodes. Each line contains G and C, each 0 or 1. If G is 1 the gate on this node is an AND gate, and if G is 0 it is an OR gate. If C is 1 the gate on this node can be changed, and if C is 0 it cannot. The two children of interior node $X$ are node $2X$ and node $2X+1$.

The remaining $(M+1)/2$ lines describe the leaf nodes. Each line contains that leaf's value I, 0 or 1.

Here is a picture of the tree given in case 1 of the first example.

Limits

• $2 \le N \le 20$
• $3 \le M \le 9999$, and M is odd

For each test case, print one line in this format.

Case #X: Y

X is the number of the test case and Y is the minimum number of gates that must be changed to make the root hold V. If the root cannot be made to hold V, print IMPOSSIBLE in place of Y.

In case 1 of the first example, changing the gate on node 3 to an OR gate makes the root hold the desired value.

In case 2, only the root can be changed, and changing it to an OR gate leaves the root's value unchanged.