거짓말쟁이 찾기

$n \ge 2$명의 사람이 $1, 2, \dots, n$번으로 번호가 매겨져 있습니다. 각 사람은 참말쟁이(진실만 말하는 사람) 또는 거짓말쟁이이며, 거짓말쟁이의 수는 $t$ 이하입니다($t \le n$).

임의의 사람 $i$는 다른 사람 $j$를 검사하여 $j$가 참말쟁이인지 거짓말쟁이인지 판정할 수 있습니다. 검사 결과 $a_{i,j}$는 사람 $i$가 $j$를 거짓말쟁이라고 판정하면 $1$, 참말쟁이라고 판정하면 $0$입니다. 이 결과는 검사한 사람 $i$가 참말쟁이일 때에만 신뢰할 수 있습니다. 즉 $i$가 거짓말쟁이이면 결과는 신뢰할 수 없어 $0$ 또는 $1$ 어느 값이든 될 수 있습니다. 결과 값을 정리하면 다음과 같습니다.

검사는 원형으로 이루어집니다. 사람 $1$이 사람 $2$를, 사람 $2$가 사람 $3$을, $\dots$, 사람 $n-1$이 사람 $n$을, 그리고 사람 $n$이 사람 $1$을 검사합니다. 이 결과들로부터 어떤 사람은 반드시 거짓말쟁이임이 확정되지만, 어떤 사람은 거짓말쟁이일 수도 아닐 수도 있습니다. $n$, $t$, 그리고 검사 결과가 주어질 때 반드시 거짓말쟁이인 사람을 모두 찾으세요.

예를 들어 $n = 5$, $t = 2$이고 결과 $(a_{1,2}, a_{2,3}, a_{3,4}, a_{4,5}, a_{5,1})$가 $(0, 1, 1, 0, 0)$이라고 합시다. 사람 $3$은 반드시 거짓말쟁이입니다. 만약 사람 $3$이 참말쟁이라면 결과를 따라갈 때 사람 $1$, $4$, $5$도 모두 거짓말쟁이가 되어 거짓말쟁이가 $3$명 이상이 되고, 이는 $t = 2$에 어긋납니다. 따라서 사람 $3$은 확정된 거짓말쟁이입니다. 반면 거짓말쟁이 집합이 ${3, 4}$일 수도 ${3}$일 수도 있으므로 사람 $4$를 거짓말쟁이라고 확정할 수는 없습니다.

주어진 결과는 거짓말쟁이가 $t$명 이하인 어떤 배치에서 나온 것이라고 가정해도 됩니다.

첫째 줄에 테스트 케이스의 수 $T$가 주어집니다. 각 테스트 케이스는 두 줄로 이루어집니다. 첫째 줄에는 두 정수, 사람 수 $n$($1 \le n \le 1000$)과 거짓말쟁이의 최대 수 $t$($0 \le t \le n$)가 주어집니다. 둘째 줄에는 $0$ 또는 $1$인 $n$개의 값이 $a_{1,2}, a_{2,3}, \dots, a_{n-1,n}, a_{n,1}$ 순서로 주어집니다.

각 테스트 케이스마다 한 줄에 두 정수를 출력합니다. 첫째 정수는 확정된 거짓말쟁이의 수, 둘째 정수는 확정된 거짓말쟁이 중 가장 작은 번호입니다. 확정된 거짓말쟁이가 없으면 둘째 정수로 $0$을 출력합니다.