P8899 [USACO22DEC] Reverse Engineering B

Elsie has a program that takes as input an array of $N$ variables ($1 \le N \le 100$), $b[0], \cdots, b[N-1]$, where each variable equals $0$ or $1$, and returns the result of applying a sequence of `if / else if / else` statements to the input. Each branch checks at most one input variable and returns $0$ or $1$. An example of such a program is: ```cpp if (b[1] == 1) return 1; else if (b[0] == 0) return 0; else return 1; ``` For example, if the input to the program above is "10" (i.e., $b[0] = 1$ and $b[1] = 0$), then the output should be $1$. Elsie told Bessie the correct outputs for $M$ different inputs ($1 \le M \le 100$). Bessie is now trying to reverse engineer Elsie’s program. Unfortunately, Elsie may have lied; there might be no program of the above form whose behavior matches everything Elsie said. For each of $T$ test cases ($1 \le T \le 10$), determine whether Elsie is certainly lying.

The first line contains $T$, the number of test cases. For each test case, the first line contains two integers $N$ and $M$. Each of the following $M$ lines contains a string of $N$ characters, each $0$ or $1$, representing an input (the values of $b[0] \cdots b[N-1]$), followed by another character ($0$ or $1$) representing the output. Consecutive test cases are separated by a blank line.

For each test case, output a single line containing $\texttt{OK}$ or $\texttt{LIE}$, indicating respectively that Elsie might not be lying or is certainly lying.

### Explanation for Sample 1 Here is one valid program for the first test case: ```cpp if (b[0] == 0) return 0; else return 1; ``` Here is another valid program for the first test case: ```cpp if (b[0] == 1) return 1; else return 0; ``` Here is one valid program for the second test case: ```cpp if (b[1] == 1) return 1; else if (b[0] == 0) return 0; else return 1; ``` Clearly, no valid program exists for the third test case, since Elsie’s program must always produce the same output for the same input. It can be proven that no valid program exists for the last test case. ### Properties of test points - Test points $2$–$3$ satisfy $N = 2$. - Test points $4$–$5$ satisfy $M = 2$. - Test points $6$–$12$ have no additional constraints. Translated by ChatGPT 5