시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.3 초 1024 MB 24 7 6 35.294%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

4 2
3 1 2 3
2 2 4

예제 출력 1

1

예제 입력 2

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10

예제 출력 2

7

예제 입력 3

2 1
2 1 2

예제 출력 3

1

예제 입력 4

15 7
3 1 2 3
3 4 2 5
3 6 2 7
3 8 2 9
3 10 2 11
3 12 2 13
3 14 2 15

예제 출력 4

1

예제 입력 5

6 1
7 1 2 5 6 2 3 4

예제 출력 5

3

예제 입력 6

8 2
5 1 2 3 4 7
5 4 5 6 1 8

예제 출력 6

4

노트

출처