해리 포터와 벡터 주문

해리 포터가 혼혈 왕자의 일기에서 또 하나의 이상한 주문을 찾아냈다. 이 주문은 크기가 $M$인 이진 벡터를 만들어 낸다. 해리의 실력이 아직 부족해서 주문이 완벽하게 작동하지 않고, 0이 아닌 원소가 정확히 2개인 벡터만 만들어진다.

해리는 이 주문을 $N$번 썼고, 만들어진 벡터를 모두 열로 세워 $M$행 $N$열 행렬을 만들었다.

마법 행렬 이론 수업에서 교수가 이 행렬의 랭크를 구하라는 문제를 냈다. 해리를 도와주자.

마법 행렬 이론의 연산은 다음 규칙을 따른다.

행렬 $A$의 랭크는 $A$의 열 가운데 선형독립인 열의 최대 개수다. 집합 $T = \{\vec{v_1}, \vec{v_2}, \dots, \vec{v_k}\}$에 속한 벡터가 선형독립이라는 것은, $a_i \in \{0, 1\}$일 때 방정식 $a_1\vec{v_1} + a_2\vec{v_2} + \dots + a_k\vec{v_k} = \vec{0}$이 성립하는 경우가 $a_1 = a_2 = \dots = a_k = 0$뿐이라는 뜻이다.

첫째 줄에 벡터의 크기 $M$과 해리가 만든 벡터의 개수 $N$이 주어진다.

다음 $M$개 줄에는 $k_i$, $c_1$, $c_2$, $\dots$, $c_{k_i}$ 형식으로 주어진다. $k_i$는 $i$번째 행에서 0이 아닌 원소의 개수이고, 이어지는 $k_i$개의 수는 그 행에서 0이 아닌 열의 번호 $c_j$다 ($1 \le c_j \le N$, $j = 1, \dots, k_i$).

• $1 \le N \le 10^5$
• $2 \le M \le 10^5$
• $0 \le k_i \le N$
• 각 열에는 0이 아닌 원소가 정확히 2개 있다.

첫째 줄에 행렬의 랭크를 출력한다.

첫 번째 예제에서 해리가 만든 벡터는 세 개다.

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

행렬은 다음과 같다.

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

그런데 $\vec{v_1} + \vec{v_2} + \vec{v_3} = \vec{0}$이다.