일 배정

시간 제한2초메모리 제한256 MB

요약
N명의 직원에게 각자 할 수 있는 일 중 최대 한 개를 맡겨 끝낼 수 있는 일 수를 구합니다.
난이도

보통10점 중 4점

유형
그래프, DFS
정답자
아직 제출이 없습니다

문제

강호네 회사에는 직원이 N명 있고, 처리해야 할 일이 M개 있다. 직원은 1번부터 N번까지, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 자신이 할 수 있는 일 중에서 한 개만 맡을 수 있고, 하나의 일은 한 명만 맡을 수 있다.

직원마다 할 수 있는 일의 목록이 주어질 때, M개의 일 중에서 최대 몇 개를 처리할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개의 줄에 걸쳐 각 직원의 정보가 주어진다. 그중 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 그 일의 번호가 차례로 주어진다. 할 수 있는 일이 하나도 없는 직원의 줄에는 0만 주어진다. 한 줄에 같은 일 번호가 두 번 나오지는 않는다.

출력

첫째 줄에 강호네 회사에서 처리할 수 있는 일의 최대 개수를 출력한다.

예제8

  1. 예제 1

    입력
    5 5
2 1 2
1 1
2 2 3
3 3 4 5
1 1
    예상 출력
    4

  2. 예제 2

    입력
    1 1
0
    예상 출력
    0

  3. 예제 3

    입력
    1 1
1 1
    예상 출력
    1

  4. 예제 4

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

  5. 예제 5

    입력
    4 4
2 1 2
2 2 3
2 3 4
1 4
    예상 출력
    4

  6. 예제 6

    입력
    5 2
2 1 2
2 1 2
2 1 2
2 1 2
2 1 2
    예상 출력
    2

  7. 예제 7

    입력
    2 5
5 1 2 3 4 5
5 1 2 3 4 5
    예상 출력
    2

  8. 예제 8

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