题目描述

有 $n \geq 2$ 个人，编号为 $1, 2, \dots, n$，每个人要么是诚实者，要么是说谎者，且说谎者的数量不超过某个给定的 $t$（$t \leq n$）。

每个人 $i$ 可以测试另一个人 $j$，通过提问来判断 $j$ 是诚实者还是说谎者。测试结果 $a_{i,j}$ 的值如下：

• 如果 $i$ 认为 $j$ 是说谎者，则 $a_{i,j} = 1$；
• 如果 $i$ 认为 $j$ 是诚实者，则 $a_{i,j} = 0$。

测试结果 $a_{i,j}$ 可靠，当且仅当测试者 $i$ 是诚实者；否则，$a_{i,j}$ 不可靠（即 $i$ 是说谎者时，$a_{i,j}$ 可能是 $0$ 或 $1$）。具体关系如下表：

测试过程是环形进行的：

1. 人 $1$ 测试人 $2$；
2. 人 $2$ 测试人 $3$；
3. $\dots$
4. 人 $n-1$ 测试人 $n$；
5. 人 $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$ 是诚实者，则人 $4$ 和人 $2$ 必须是说谎者，进而导致人 $1$ 和人 $5$ 也必须是说谎者，但这样总说谎者数量超过 $t = 2$，矛盾。因此，人 $3$ 一定是说谎者。
• 但人 $4$ 可能是说谎者，也可能不是，因此不能确定。

任务

给定 $n$、$t$ 和测试结果，找出所有一定是说谎者的人。题目保证输入的测试结果至少对应一种说谎者数量不超过 $t$ 的情况。

输入

输入包含 $T$ 个测试用例。第一行给出测试用例数量 $T$。每个测试用例包含两行：

1. 第一行：$n$（人数，$2 \leq n \leq 1000$）和 $t$（最多说谎者数量，$0 \leq t \leq n$）；
2. 第二行：$n$ 个 $0$ 或 $1$，表示测试结果 $(a_{1,2}, a_{2,3}, \dots, a_{n-1,n}, a_{n,1})$。

输出

每个测试用例输出一行，包含两个整数：

1. 一定是说谎者的人数；
2. 这些说谎者中最小的编号。
   如果没有一定是说谎者的人，则输出 $0$ $0$。

输入样例

3
5 2
0 1 1 0 0
7 2
0 0 1 0 0 1 1
9 8
1 0 0 0 0 1 0 0 0

输出样例

1 3
2 4
0 0

题目来源

Taejon 2002