16859번 - 선인장의 최대 매칭

그래프에서 서로 붙어 있지 않은 (끝점을 공유하지 않는) 최대 크기의 간선 부분집합을 매칭 이라고 부른다.

임의의 서로 다른 두 단순 사이클이 최대 하나의 공통 정점을 가지는 무방향 “단순” 연결 그래프를 선인장 그래프 라고 부른다.

선인장 그래프에서 최대 매칭을 계산하라.

첫 줄에는 정점의 개수 N (1 ≤ N ≤ 50,000)과 간선의 집합 개수 M (0 ≤ M ≤ 50,000)이 주어진다.

다음 M개의 줄에 M개의 간선의 집합에 대한 정보가 주어지는데, 각 줄에 첫 번째 수 K_i (1 ≤ K_i ≤ 1,000)는 i번째 에지 집합의 개수를 나타낸다. 다음 K_i개의 수는 정점의 번호를 나타내는데 인접한 두 정점간의 에지가 집합에 포함되는 것을 의미한다.

선인장 그래프의 최대 매칭의 크기를 출력하라.