← 返回题目列表

Codeforces · 1277/D

D. 让我们玩文字游戏吧?

中文机器翻译题面 查看原题

Polycarp 有 $$$n$$$ 个不同的二进制字。如果一个单词仅包含字符“0”和“1”,则该单词称为二进制。例如,这些字是二进制的:“0001”、“11”、“0”和“0011100”。

Polycarp 想要提供他的一组 $$$n$$$ 二进制单词来玩“单词”游戏。在这个游戏中,玩家命名单词,并且下一个单词(从第二个开始)必须从前一个单词的最后一个字符开始。第一个单词可以是任何单词。例如,在游戏过程中可以命名这些单词序列:“0101”、“1”、“10”、“00”、“00001”。

字反转是将字符顺序颠倒的操作。例如,单词“0111”反转后变为“1110”,单词“11010”反转后变为“01011”。

很可能,波利卡普有这样一组单词,以至于无法按照游戏规则将它们按照顺序排列。在这种情况下,他想反转他的集合中的一些单词,以便:

- 最终的 $$$n$$$ 单词集仍然包含不同的单词(即所有单词都是唯一的);
- 有一种方法可以将最终单词集中的所有单词按顺序排列,使得$$$n$$$单词的最终序列符合游戏规则。

Polycarp 想要反转最少数量的单词。请帮助他。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — Polycarp 集合中的单词数。接下来的 $$$n$$$ 行包含这些单词。所有 $$$n$$$ 单词都不为空,并且仅包含字符“0”和“1”。字长总和不超过$$$4\cdot10^6$$$。所有的词都是不同的。

保证输入中所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。另外,保证输入中所有测试用例的字长总和不超过 $$$4\cdot10^6$$$。

输出

按出现的顺序打印所有 $$$t$$$ 测试用例的答案。

如果测试用例没有答案,则打印 -1。否则,输出的第一行应包含 $$$k$$$ ($$$0 \le k \le n$$$) — 集合中应反转的最小单词数。输出的第二行应包含 $$$k$$$ 不同的整数 - 集合中应反转的单词的索引。单词按照出现的顺序从 $$$1$$$ 到 $$$n$$$ 进行编号。如果 $$$k=0$$$ 你可以跳过这一行(或者你可以打印一个空行)。如果有很多答案,您可以打印其中任何一个。

示例

输入 #1

4
4
0001
1000
0011
0111
3
010
101
0
2
00000
00001
4
01
001
0001
00001

输出 #1

1
3 
-1
0

2
1 2