CF1250E The Coronation

贝尔二十二世国王的加冕典礼即将举行！整个王室家族，包括贝尔二十二世的 $n$ 位女儿都将出席。 国王已经命令他的珠宝匠制作 $n$ 条精美的项链，以便每位公主在典礼上都能佩戴一条项链——现在这些项链已经完成。每条项链由 $m$ 颗宝石串在金链上组成。项链上只使用了两种宝石——祖母绿和蓝宝石。因此，每条项链可以用一个长度为 $m$ 的宝石序列表示（从左到右排列），每颗宝石要么是祖母绿，要么是蓝宝石。形式化地说，第 $i$ 条项链可以用一个长度为 $m$ 的二进制字符串 $s_i$ 表示；如果 $s_i$ 的第 $j$ 个字符是 $0$，则第 $i$ 条项链的第 $j$ 颗宝石是祖母绿，否则是蓝宝石。 现在，国王担心有些女儿会嫉妒其他女儿的项链。他希望所有项链看起来都很相似。两条项链被认为是相似的，当且仅当它们在至少 $k$ 个位置上拥有相同类型的宝石。 例如，有一条项链的序列为 $01010111$，另一条为 $01100000$，那么这两条项链在 $3$ 个位置上拥有相同类型的宝石（第一颗都是祖母绿，第二颗都是蓝宝石，第五颗都是祖母绿）。所以如果 $k=3$，这两条项链是相似的；如果 $k=4$，则不相似。 国王认为，如果他的两个女儿发现她们的项链不相似，就可能发生冲突——而他显然不希望在加冕典礼上出现任何冲突！因此，贝尔二十二世打算让部分女儿将项链反着佩戴。如果一条项链反着戴，那么它的宝石序列就会被反转。例如，原本为 $01100$ 的项链，反着戴后就是 $00110$。国王希望找到在加冕典礼上最少需要反着佩戴的项链数量，使得不会发生任何冲突。 贝尔二十二世正忙于加冕典礼的准备工作，因此他让你来解决这个问题。请帮助他——他会给你真正的皇家奖励！

第一行包含一个整数 $t$（$1 \le t \le 50$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 50$，$1 \le k \le m \le 50$），分别表示项链的数量、每条项链的宝石数量，以及两条项链被认为相似所需的最少相同宝石位置数。 接下来的 $n$ 行，每行一个长度为 $m$ 的二进制字符串 $s_i$，表示第 $i$ 条项链。

对于每个测试用例，按如下格式输出答案。 如果无法避免冲突，输出一行 $-1$。在这种情况下，不要为该测试用例输出其他内容。 否则，第一行输出一个整数 $d$，表示最少需要反着佩戴的项链数量。第二行输出这 $d$ 条项链的编号（编号为 $1$ 到 $n$，顺序任意）。如果 $d=0$，则第二行留空。如果有多种答案，可以输出任意一种。

由 ChatGPT 4.1 翻译