Gates

In the modern VLSI chip industry, the software tools used by electrical engineers perform many optimizations. Your task is to implement one specific optimization of a chip design.

Your tool is given an acyclic net of NAND gates. (A NAND gate computes the negated conjunction of its inputs: the gate's output is 0 if and only if both of its input values are 1.) The net is part of an already-synthesized component and cannot be changed. All inputs of the net are connected to a single signal x. The objective is to disconnect x from some inputs and drive those inputs with the constant signals 0 and/or 1, so that the function implemented by the design stays unchanged.

We say that an assignment of x's, 0's, and 1's to the inputs of the net is optimal when the number of inputs still connected to x is the smallest possible while the net computes the same function it computes when all inputs are connected to x.

Consider the following design.

It can be redriven so that only one input remains variable, for example:

(There are also other ways of driving the inputs with a single x plus some 0's and 1's that implement the same function.)

Because the whole net realizes a Boolean function of the single variable x, that function is either constant (the same for x = 0 and x = 1) or non-constant. In an optimal assignment the number of inputs connected to x is therefore 0 when the function is constant and 1 when it is non-constant.

Write a program that, for each data set:

• reads the description of the net,
• determines the smallest number of inputs that must remain connected to x,
• writes that number.

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 ≤ d ≤ 20. The data sets follow.

Each data set consists of two consecutive lines. The first of those lines contains exactly two positive integers n and m separated by a single space, 1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000. Integer n is the number of net inputs and integer m is the number of gates in the net.

The second of those lines contains exactly 2m nonzero integers, separated by single spaces. The numbers at positions 2j − 1 and 2j describe the signal sources for the two inputs of gate j. A positive number s means the output of gate s. A negative number s means the (−s)-th input of the net. Gates and net inputs are numbered starting from one. Each gate input is connected either to a net input or to the output of a gate whose description occurred earlier in the sequence. Each net input is connected to at least one gate input. Each gate output is connected to at least one gate input, except the output of the last gate, which is connected to the output of the net.

The output should consist of exactly d lines, one line for each data set. Line number i contains the answer for the i-th data set: a single integer equal to the smallest number of net inputs that must remain connected to x so that the net still computes the same function it computes when every input is connected to x. This value is 0 when the net's function does not depend on x and 1 when it does.