409714: GYM103698 D Matrix

A member of My Little Pony, Pony Yaya, is a pony who loves matrices. He has tried to combine matrices with many other OI techniques, and today he wants to combine matrices with $$$\mathbb{F}_2$$$.

Pony Yaya finds a $$$01$$$ matrix $$$L$$$ of $$$n \times n$$$, and initially, all entries of $$$L$$$ are $$$0$$$.

Pony Yaya wants to do something with it. Each operation selects a number $$$p \in [1,n]$$$, and then flips the numbers in the $$$p$$$-th row and $$$p$$$-th column of the matrix $$$L$$$ respectively ($$$0$$$ becomes $$$1$$$, $$$1$$$ becomes $$$0$$$). Note that $$$L_{p,p}$$$ will be flipped twice, so the value of $$$L_{p,p}$$$ will not change.

Pony Yaya has certain expectations for certain entried. Specifically, he will give a $$$01$$$ matrix $$$A$$$ of $$$n \times n$$$, if the position $$$(i, j)$$$ satisfies $$$A_{i,j} = 1$$$, it means that Pony Yaya hopes $$$L_{i,j} = 0$$$. Otherwise, it means that he has no demand for $$$L_{i,j}$$$.

Pony Yaya wants to make $$$L$$$ meet all his needs through several operations, but unfortunately, his matrix skills are not superb enough. So he finds you, hoping you can meet all his needs.

In order to let you show your advanced matrix skills, he also wants you to give a solution with the smallest number of operations, and in that premise, he also wants you to give the sequence of operations with the smallest lexicographical order.

Definition of lexicographical order: For two operation sequences $$$a, b$$$ of length $$$k$$$, lexicographical order $$$a < b$$$ if and only if $$$\exists \ i\in[1,k]$$$ satisfies $$$a_i < b_i$$$ and $$$\forall j < i, a_j = b_j$$$.

The first line contains a positive integer $$$n$$$.

For the second line to the $$$(n+1)$$$-th line, each line contains a $$$01$$$ string of length $$$n$$$. The $$$j$$$-th character in $$$i+1$$$-th line represents the value of $$$A_{i,j}$$$.

If no operation sequence can meet Pony Yaya's needs, output $$$-1$$$.

Otherwise, output two lines.

The first line contains an integer $$$k$$$, representing the minimum number of operations.

The second line contains a sequence $$$p_i$$$ of length $$$k$$$, represent the operation sequence. There is a space between every two adjacent integers.

You need to ensure that the lexicographical order of the $$$p$$$ sequence is minimum in the premise that $$$k$$$ is minimum.

4
0101
1010
0101
1010

2
1 3 

6
011001
100011
100110
001000
011000
110000

-1

7
0110000
0000000
1000100
0100010
0000010
0001000
1000000

3
1 4 5 

Subtask 1 (10pts): $$$n \le 4$$$.

Subtask 2 (20pts): $$$n \le 10$$$.

Subtask 2 (20pts): $$$n \le 500$$$.

Subtask 3 (50pts): No special restrictions.

For $$$100\%$$$ of data, $$$n \le 5000$$$.