15396번 - Harry Potter and The Vector Spell 다국어

Harry Potter has found another strange spell in Half-blood Prince diary, that could generate a different binary vector of size M. As he is not the best magician, this spell does not work perfectly so he could generate only vectors where exactly 2 elements are non zero. Harry has used this spell N times and he has constructed a matrix of M rows and N columns, where all generated vectors are columns.

Now Harry has a class of Magical Matrix Theory, where the professor asked him to calculate the rank of such a matrix. You are here to help him!

Operations in Magical Matrix Theory satisfied next rules:

The rank of a matrix A corresponds to the maximal number of linearly independent columns of A. The vectors in a set \(T = \{\vec{v_1}, \vec{v_2}, \dots, \vec{v_k}\}\) are said to be linearly independent if the equation \(a_1\vec{v_1} + a_2\vec{v_2} + \dots + a_k\vec{v_k} = \vec{0}\), where \(a_i = \{0, 1\}\) for \(i = 1, \dots, k\) can only be satisfied by \(a_i = 0\) for \(i = 1, \dots, k\).

On the first line two integers - M (size of vectors) and N (number of vectors generated by Harry). Each of the next M lines has the format: k_i, c₁, c₂, ..., c_ki, where k_i is the number of non-zero elements in row i. The next k_i numbers are column indexes (1 ≤ c_j ≤ N, j = 1, ..., k_i), which are non-zero in this row. For more details, see exampels.

• 1 ≤ N ≤ 10⁵
• 2 ≤ M ≤ 10⁵
• 0 ≤ k_i ≤ N

In first example, Harry has generated 3 vectors:

\(\vec{v_1} = (1, 1, 0), \vec{v_2} = (0, 1, 1), \vec{v_3} = (1, 0, 1)\)

and the matrix is:

\begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix}

But \(\vec{v_1} + \vec{v_2} + \vec{v_3} = \vec{0}\).