CHIP company manufactures combinational circuits built using only 2-input AND, 2-input OR and 1-input NOT gates. Circuits can have n (at most 30) primary input wires (labelled from 1 to n) and m (at most 10) output wires (labelled from 1 to m). You are hired to write a program to help automate testing of their hardware circuits. Your program should read, for each circuit to be tested, a description of the circuit and desired values (bit vector) at the m output lines. It should then print how many possible input vectors can produce that particular output. If the desired output cannot be produced by any input combination, print 0.
Input
The first line will be number of circuits to be tested.
It will be followed by data for each circuit ending with a line containing -1.
That is data for first circuit, then a line containing -1, then data for second circuit and so on.
For each circuit, the data contains its description followed by test cases.
The first line of the description will contain
the number of primary inputs (n) and number of primary outputs (m) for this circuit
(2 numbers separated by a space).
The next line contains the number of gates (k) used in this circuit.
This is followed by k lines (one per gate)
describing each gate in the following format.
First number is the Gate Number, the second number is the Gate-Type (1=And, 2=Or, 3=Not), followed by
one number for each input wire of this gate showing where that input wire is connected.
A negative number (-4 say) means this input comes from the output of gate 4.
A positive number (3 say) means this input comes from primary input wire 3.
After these numbers for input wires, there is one last number
indicating whether the output of this gate
is connected to some other gate's input (denoted by 0).
or it is a primary output
(denoted by 
the number of the output wire).
The circuit description is followed by test cases (one per line)
for desired values on the output wires. If a circuit has m output wires,
a test case will be m numbers (0 or 1) separated by a single space
representing the values at wires 1 to m.
The first circuit in the sample input given below implements XOR function on 2 inputs.
Output
For each test case in each circuit, print one number (on a separate line, no blank lines) which indicates how many possible input combinations can produce that output. Print 0 if the test case output is not achievable with the circuit.
|
|