축사 배정
면접 대비시간 제한2초메모리 제한128 MB
각 소가 원하는 축사 목록이 주어질 때, 서로 다른 축사에 배정 가능한 소의 최대 수를 이분 매칭으로 구합니다.
문제
농부 존은 소를 넣을 축사를 완성했다. 쾌적한 환경을 유지하기 위해 축사를 M개의 칸으로 나누었고, 각 칸에는 소를 최대 한 마리만 넣을 수 있다.
처음에는 소를 임의로 배정했지만, 곧 문제가 생겼다. 각 소는 자신이 원하는 칸 목록에 있는 칸에만 들어가려고 하고, 그 밖의 칸에는 들어가려 하지 않는다.
각 소가 들어갈 수 있는 칸의 목록이 주어질 때, 축사에 배정할 수 있는 소의 최대 수를 구하시오. 축사 칸의 번호는 1부터 M까지이다.
입력
첫째 줄에 소의 수 N과 축사 칸의 수 M이 주어진다. (1 ≤ N, M ≤ 200)
다음 N개의 줄에는 각 소가 원하는 칸의 정보가 주어진다. i번째 소에 대해, 먼저 원하는 칸의 수 S_i (0 ≤ S_i ≤ M)가 주어지고, 이어서 S_i개의 서로 다른 칸 번호가 주어진다.
출력
축사에 배정할 수 있는 소의 최대 수를 출력한다.