1971: [USACO 2022 December Contest Bronze] Problem 3. Reverse Engineering

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" (that is, $b[0]=1$ and $b[1]=0$), then the output should be 1.

Elsie has told Bessie the correct output for $M$ ($1\le M\le 100$) different inputs. Bessie is now trying to reverse engineer Elsie's program. Unfortunately, Elsie might have lied; it may be the case that no program of the form above is consistent with what Elsie said.

For each of $T$ ($1\le T\le 10$) test cases, determine whether Elsie must be lying or not.

Each test case starts with two integers $N$ and $M$, followed by $M$ lines, each containing a string of $N$ zeros and ones representing an input (that is, the values of $b[0]\dots b[N-1]$) and an additional character (zero or one) representing the output. Consecutive test cases are separated by newlines.

4

1 3
0 0
0 0
1 1

2 4
00 0
01 1
10 1
11 1

1 2
0 1
0 0

2 4
00 0
01 1
10 1
11 0

OK
OK
LIE
LIE