Reverse-Engineering Elsie’s If/Else Program

Elsie wrote a program that takes an array of N boolean variables b[0], b[1], ..., b[N-1] (each either 0 or 1) and returns a single boolean value (0 or 1) by applying a series of if / else if / else statements. In each statement at most one variable is checked (i.e. a condition of the form \( b[i] = c \) with \( c \in \{0,1\} \)) and the statement returns a fixed value 0 or 1. For example, a program might look like:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

Given an input string such as "10" (i.e. \( b[0]=1 \) and \( b[1]=0 \)), this program would output \( 1 \).

Elsie provided Bessie with the correct outputs for M different inputs. However, Elsie might be lying – there might not exist any if/else program in the above form that would produce exactly the outputs Elsie claimed.

Your task is: for each sub-test case (there are \( T \) of them) decide whether Elsie’s responses can be produced by some if/else program of the described form. If such a program exists, print OK; otherwise, print LIE.

The if/else program is assumed to work as follows. It consists of a sequence of rules of the form:

[ \texttt{if (b[i]==c) return r;} ]

followed by a final else that returns some constant. When an input is provided, the program scans the rules from top to bottom and returns the output of the first rule whose condition is satisfied; if none are satisfied, it returns the result in the final else branch.

You are given the parameters \(N\) (number of variables) and \(M\) (number of input/output pairs). All \(M\) inputs are distinct and each input is provided as a binary string of length \(N\). The desired output for each input is also given.

Hint: One way to decide whether a valid if/else program exists is to try to "cover" the given input set by rules. A rule of the form "if (b[i]==v) return r" will cover all inputs that have the same value \( v \) in position \( i \). Such a rule is valid only if all covered inputs require the same output \( r \). You may repeatedly remove groups of inputs covered by some valid rule. If you can remove all inputs by this process, then a valid if/else program exists; otherwise, Elsie must be lying.

inputFormat

The first line of input contains an integer \(T\) (1 ≤ \(T\) ≤ 10), the number of test cases. Each test case begins with a line containing two integers \(N\) (1 ≤ \(N\) ≤ 100) and \(M\) (1 ≤ \(M\) ≤ 100), indicating the number of variables and the number of input/output pairs respectively. The following \(M\) lines each contain a binary string of length \(N\) and an integer (0 or 1), separated by a space, representing an input and its corresponding output. All input binary strings in a test case are distinct.

Sample Input:

3
2 3
00 0
01 0
10 1
2 3
00 0
01 1
10 1
2 4
00 0
01 1
10 1
11 0

outputFormat

For each test case, output a single line containing either OK if there exists an if/else program (as described) that produces exactly the given outputs, or LIE if no such program exists.

Sample Output:

OK
OK
LIE

sample

3
2 3
00 0
01 0
10 1
2 3
00 0
01 1
10 1
2 4
00 0
01 1
10 1
11 0

OK
OK
LIE

</p>