선인장의 최대 매칭

시간 제한0.3초메모리 제한1024 MB

요약

정점 목록으로 주어진 선 집합들로 이루어진 캑터스 그래프에서 최대 매칭의 크기를 구합니다.

난이도: 보통10점 중 6점
유형: 트리, 동적 계획법, 그래프
정답자: 아직 제출이 없습니다

문제

그래프에서 어떤 두 간선도 끝점을 공유하지 않는 간선들의 집합을 매칭이라고 부른다. 간선의 개수가 가장 많은 매칭을 최대 매칭이라고 한다.

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

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

입력

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

다음 $M$ 개의 줄에 간선 집합에 대한 정보가 주어진다. 각 줄의 첫 번째 수 $K_i$ ( $1 \\le K_i \\le 1{,}000$ )는 $i$ 번째 간선 집합에 포함된 정점의 개수이다. 이어지는 $K_i$ 개의 수는 정점의 번호이며, 인접한 두 정점 사이의 간선이 집합에 포함됨을 뜻한다.

출력

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

예제5

예제 1
입력
```
4 2
3 1 2 3
2 2 4
```
예상 출력
```
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

예상 출력

예제 3
입력
```
2 1
2 1 2
```
예상 출력
```
1
```

예제 4

입력

예상 출력

예제 5
입력
```
6 1
7 1 2 5 6 2 3 4
```
예상 출력
```
3
```