Finding Liars

There are $n \ge 2$ people labeled $1, 2, \dots, n$. Each person is either a truth-teller or a liar, and the total number of liars is at most $t$ (with $t \le n$).

Any person $i$ can test another person $j$ and report whether $j$ is a truth-teller or a liar. The outcome $a_{i,j}$ is $1$ if person $i$ reports that $j$ is a liar, and $0$ if person $i$ reports that $j$ is a truth-teller. A report is reliable exactly when the tester $i$ is a truth-teller; if the tester $i$ is a liar, the report is unreliable and may take either value. The outcomes are summarized below.

Testing is arranged in a circle: person $1$ tests person $2$, person $2$ tests person $3$, $\dots$, person $n-1$ tests person $n$, and person $n$ tests person $1$. From the outcomes, some people are guaranteed to be liars, while others may or may not be liars. Given $n$, $t$, and the outcomes, determine which people are definitely liars.

For example, let $n = 5$, $t = 2$, and let the outcomes $(a_{1,2}, a_{2,3}, a_{3,4}, a_{4,5}, a_{5,1})$ be $(0, 1, 1, 0, 0)$. Person $3$ must be a liar: if person $3$ were a truth-teller, then following the reports forces persons $1$, $4$, and $5$ to be liars as well, giving at least three liars and contradicting $t = 2$. So person $3$ is a definite liar. However, both ${3, 4}$ and ${3}$ are possible liar sets, so person $4$ cannot be pinned down as a definite liar.

You may assume the given outcomes come from some assignment that has at most $t$ liars.

The first line contains the number of test cases $T$. Each test case has two lines. The first line has two integers: $n$ ($1 \le n \le 1000$), the number of people, and $t$ ($0 \le t \le n$), the maximum number of liars. The second line has $n$ values, each $0$ or $1$, giving $a_{1,2}, a_{2,3}, \dots, a_{n-1,n}, a_{n,1}$ in this order.

For each test case, print one line with two integers: the number of definite liars, and the smallest label among the definite liars. If there are no definite liars, print $0$ as the second integer.