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