Let's Play the Words?
Contest: Technocup 2020 - Elimination Round 4
Difficulty rating: 1900
Tags: data structures, hashing, implementation, math

Polycarp has $$$n$$$ different binary words. A word called binary if it contains only characters '0' and '1'. For example, these words are binary: "0001", "11", "0" and "0011100".

Polycarp wants to offer his set of $$$n$$$ binary words to play a game "words". In this game, players name words and each next word (starting from the second) must start with the last character of the previous word. The first word can be any. For example, these sequence of words can be named during the game: "0101", "1", "10", "00", "00001".

Word reversal is the operation of reversing the order of the characters. For example, the word "0111" after the reversal becomes "1110", the word "11010" after the reversal becomes "01011".

Probably, Polycarp has such a set of words that there is no way to put them in the order correspondent to the game rules. In this situation, he wants to reverse some words from his set so that:

- the final set of $$$n$$$ words still contains different words (i.e. all words are unique);
- there is a way to put all words of the final set of words in the order so that the final sequence of $$$n$$$ words is consistent with the game rules.

Polycarp wants to reverse minimal number of words. Please, help him.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow.

The first line of a test case contains one integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — the number of words in the Polycarp's set. Next $$$n$$$ lines contain these words. All of $$$n$$$ words aren't empty and contains only characters '0' and '1'. The sum of word lengths doesn't exceed $$$4\cdot10^6$$$. All words are different.

Guaranteed, that the sum of $$$n$$$ for all test cases in the input doesn't exceed $$$2\cdot10^5$$$. Also, guaranteed that the sum of word lengths for all test cases in the input doesn't exceed $$$4\cdot10^6$$$.

Output format:
Print answer for all of $$$t$$$ test cases in the order they appear.

If there is no answer for the test case, print -1. Otherwise, the first line of the output should contain $$$k$$$ ($$$0 \le k \le n$$$) — the minimal number of words in the set which should be reversed. The second line of the output should contain $$$k$$$ distinct integers — the indexes of the words in the set which should be reversed. Words are numerated from $$$1$$$ to $$$n$$$ in the order they appear. If $$$k=0$$$ you can skip this line (or you can print an empty line). If there are many answers you can print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example output:
1
3 
-1
0

2
1 2

Editorial:
For a concrete set of words, it's not hard to find a criteria for checking if there is a correct order of arrangement of words for playing a game. Let's call such sets of words correct. Firstly the set of words is correct if the number of words like 0...1 and the number of words like 1...0 differ by no more than $$$1$$$. Secondly it's correct if the number of words like 0...0 or like 1...1 is zero, because they have the same characters at the beginning and at the ending, and we can insert them in any position. And finally if words of both kinds 0...0 and 1...1 are present and there is at least one word like 0...1 or 1...0.
It can be easily proved if we note that this problem is equivalent to the Euler traversal of a directed graph with two nodes. But let's prove it without resorting to graph theory:
• if there are words of both kinds 0...0 and 1...1, but there is no words of kinds 0...1 and 1...0, starting from a word of one kind you can't go to a word of another kind. Consequently, if words of both kinds 0...0 and 1...1 are present, there should be at least one word like 0...1 or 1...0 — is a necessary condition of the problem;
• if the number of words like 0...1 and the number of words like 1...0 differ by no more than $$$1$$$, we can call them alternately starting with a kind that is larger. If these numbers are equal, we can start with any kind. And we can insert words of kind 0...0 and 1...1 at any suitable moment.
Reversals only affect the mutual number of lines of the kind 0...1 and 1...0. Therefore, immediately while reading the input data, we can check the necessary condition (first item above).
Without loss of generality we may assume that the number of words like 0...1 equals $$$n_{01}$$$ and like 1...0 equals $$$n_{10}$$$. Also we assume that $$$n_{01}>n_{10}+1$$$. Remember that all words in the current set are unique. Let's prove that we can always choose some words of kind 0...1 and reverse them so that $$$n_{01}=n_{10}+1$$$ (and at the result all words would still be unique).
In fact, the set of words of kind $$$n_{10}$$$ has no more than $$$n_{10}$$$ such words that after the reversing, the word will turn into an existing one (because it will become of type 1...0 and there are only $$$n_{10}$$$ such words). And it means that there is no less than $$$n_{01}-n_{10}$$$ words which we can reverse and get still unique word. So, we can choose any $$$n_{01}-n_{10}-1$$$ of them.
Thus, after checking of the necessary condition (first item above), we need to reverse just $$$n_{01}-n_{10}-1$$$ words of kind that is larger, which reversals aren't duplicates.
Below is an example of a possible implementation of the main part of the solution described above.