409714: GYM103698 D Matrix
Description
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$$$.
InputThe 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}$$$.
OutputIf 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.
ExamplesInput4 0101 1010 0101 1010Output
2 1 3Input
6 011001 100011 100110 001000 011000 110000Output
-1Input
7 0110000 0000000 1000100 0100010 0000010 0001000 1000000Output
3 1 4 5Note
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$$$.