최소 버텍스 커버

A와 B 두 그룹으로 나누어진 이분 그래프가 주어진다. A에는 정점이 N개, B에는 정점이 M개 있다. A의 정점에는 1번부터 N번까지, B의 정점에는 1번부터 M번까지 번호가 매겨져 있다. A의 i번 정점을 Ai, B의 j번 정점을 Bj로 나타낸다. 모든 간선은 A의 정점 하나와 B의 정점 하나를 잇는다.

버텍스 커버(vertex cover)란 정점들의 집합으로, 그래프의 모든 간선이 이 집합에 속한 정점 중 적어도 하나와 연결되도록 하는 집합이다. 즉, 집합에 속한 정점을 모두 제거하면 남는 간선이 하나도 없게 된다. 정점을 제거할 때는 그 정점에 연결된 간선도 함께 제거된다.

최소 버텍스 커버(minimum vertex cover)는 이러한 버텍스 커버 중에서 크기(정점의 개수)가 가장 작은 것을 말한다. 주어진 이분 그래프에서 최소 버텍스 커버의 크기를 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 N과 M이 주어진다. (1 ≤ N, M ≤ 1,000)

다음 N개의 줄 중 i번째 줄에는 정점 Ai와 연결된 정점의 개수 k가 먼저 주어지고, 이어서 Ai와 연결된 B 정점의 번호 j가 k개 주어진다. (연결된 정점이 없으면 0만 주어진다.)

첫째 줄에 최소 버텍스 커버의 크기를 출력한다.