3998 - M-nerdseable Sets

Created by V Copa UPR - Manuel Alejandro Diaz Perez
Added by Kino (2018-05-14)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Let S be a set of x different integers, S = {S_1, S_2, ..., S_x} and M a matrix of N * N, say that S is M-nerdseable if:
  • (1 <= S_i <= N) for all 1 <= i <= x.
  • XOR (M [S_i] [S_1], M [S_i] [S_2], ..., M [S_i] [S_x]) = 0 for all 1 <= i <= x.
  • XOR (M [S_1] [S_j], M [S_2] [S_j], ..., M [S_x] [S_j]) = 0 for all 1 <= j <= x.
Given M, a binary and symmetric matrix of N * N (1 <= N <= 300), where M[i][i]=0 for all 1 <= i <= N. Find the minimum amount of M-nerdseables sets that can be formed such that each number between 1 and N appears in exactly one of the sets.
Sea S un conjunto de x enteros diferentes, S = { S_1, S_2, ..., S_x } y M una matriz de N*N, se dice que S es M-nerdseable si:

- (1 <= S_i <= N)    para todo 1 <= i <= x.

- XOR( M[S_i][S_1] , M[S_i][S_2], ..., M[S_i][S_x] ) = 0    para todo 1 <= i <= x.

- XOR( M[S_1][S_j] , M[S_2][S_j], ..., M[S_x][S_j] ) = 0    para todo 1 <= j <= x.

Dado M, una matriz binaria y simétrica de N * N (1 <= N <= 300), donde M[i][i] = 0 para todo 1 <= i <= N.
Calcule la mínima cantidad de conjuntos M-nerdseables que se pueden formar tal que
cada número entre 1 y N aparezca en exactamente uno de los conjuntos.
;jsessionid=607DF0CEA7740DB06F97C35D2FC439CD
Let S be a set of x different integers, S = {S_1, S_2, ..., S_x} and M a matrix of N * N, say that S is M-nerdseable if:
  • (1 <= S_i <= N) for all 1 <= i <= x.
  • XOR (M [S_i] [S_1], M [S_i] [S_2], ..., M [S_i] [S_x]) = 0 for all 1 <= i <= x.
  • XOR (M [S_1] [S_j], M [S_2] [S_j], ..., M [S_x] [S_j]) = 0 for all 1 <= j <= x.
Given M, a binary and symmetric matrix of N * N (1 <= N <= 300), where M[i][i]=0 for all 1 <= i <= N. Find the minimum amount of M-nerdseables sets that can be formed such that each number between 1 and N appears in exactly one of the sets.

Input specification

The first line contains a positive integer N (N <= 300), the length of M. Each of the following N lines have N non-negative integers separated by spaces, where the j-th integer of the i-th line is the value of M[i][j]. It is guaranteed that M[i][j] <= 1 for all pairs i, j and M[i][i]=0 for all i.
La primera línea contiene un entero positivo N (N <= 300), la longitud de M.
Cada una de las siguientes N líneas tienen N enteros no negativos separados por espacios, donde el j-ésimo entero de la i-ésima línea es el valor de M[i][j]. Esta garantizado que M[i][j] <= 1 para todo par i,j y M[i][i]=0 para todo i.
;jsessionid=607DF0CEA7740DB06F97C35D2FC439CD
The first line contains a positive integer N (N <= 300), the length of M. Each of the following N lines have N non-negative integers separated by spaces, where the j-th integer of the i-th line is the value of M[i][j]. It is guaranteed that M[i][j] <= 1 for all pairs i, j and M[i][i]=0 for all i.

Output specification

If there is no solution, print a single line with -1. If there is solution, print a line with an integer MN, the minimum number of M-nerdseables sets that can be formed such that each number between 1 and N appears in exactly one of the sets. In the following MN lines print the information of each set: if the set has x elements, print x and then the elements of the set separated by spaces in any order. If there are several ways to form MN M-nerdseables sets, print any of them.
Si no existe solución imprima una sola línea con -1. De existir solución imprima una línea con un entero MN, la mínima cantidad de conjuntos M-nerdseables que se pueden formar tal que cada numero entre 1 y N aparezca en exactamente 1 de los conjuntos. En las siguientes MN líneas imprima la información de cada conjunto: si el conjunto tiene x elementos imprima x y después los elementos del conjunto separados por espacios en cualquier orden. Si existen varias maneras de formar MN conjuntos M-nerdseables imprima cualquiera de ellas.
;jsessionid=607DF0CEA7740DB06F97C35D2FC439CD
The first line contains a positive integer N (N <= 300), the length of M. Each of the following N lines have N non-negative integers separated by spaces, where the j-th integer of the i-th line is the value of M[i][j]. It is guaranteed that M[i][j] <= 1 for all pairs i, j and M[i][i]=0 for all i.

Sample input

4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Sample output

1
4 1 2 3 4

Hint(s)