CF1277D Let's Play the Words?

Polycarp 有 $n$ 个不同的二进制单词。一个单词被称为二进制单词，当且仅当它只包含字符 '0' 和 '1'。例如，“0001”、“11”、“0” 和 “0011100” 都是二进制单词。 Polycarp 想用他的 $n$ 个二进制单词来玩一个叫做“单词接龙”的游戏。在这个游戏中，玩家依次说出单词，从第二个单词开始，每个单词都必须以前一个单词的最后一个字符开头。第一个单词可以任意选择。例如，以下单词序列可以在游戏中出现：“0101”、“1”、“10”、“00”、“00001”。 单词反转是指将单词中字符的顺序颠倒。例如，“0111” 反转后变为 “1110”，“11010” 反转后变为 “01011”。 可能 Polycarp 的单词集合无法按照游戏规则排列所有单词。在这种情况下，他希望反转集合中的一些单词，使得： - 最终的 $n$ 个单词仍然互不相同（即所有单词都是唯一的）； - 存在一种排列方式，使得所有单词按照游戏规则顺序排列。 Polycarp 希望反转的单词数尽可能少。请你帮他实现这个目标。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2\cdot10^5$），表示 Polycarp 的单词数量。接下来的 $n$ 行，每行一个单词。这些单词都非空，只包含字符 '0' 和 '1'。所有单词互不相同。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$，所有单词长度的总和不超过 $4\cdot10^6$。

对于每个测试用例，按照输入顺序输出答案。 如果该测试用例无解，输出 $-1$。否则，第一行输出 $k$（$0 \le k \le n$），表示需要反转的单词最少数量。第二行输出 $k$ 个不同的整数，表示需要反转的单词在输入中的下标（单词按输入顺序从 $1$ 到 $n$ 编号）。如果 $k=0$，可以省略第二行（也可以输出一个空行）。如果有多种方案，输出任意一种即可。

由 ChatGPT 4.1 翻译