2051번 - 최소 버텍스 커버 스페셜 저지

A와 B로 나누어져 있는 이분 그래프가 입력으로 주어진다. A에는 정점이 N개가 있고, B에는 정점이 M개가 있다. 정점은 A의 정점은 1번부터 N번, B의 정점도 1번부터 M번가지 번호가 매겨져 있다. A의 i번 정점은 A_i로, B의 j번 정점은 B_j로 표시한다.

이 그래프의 최소 버텍스 커버(Minimum Vertex Cover)를 구하는 프로그램을 작성하시오.

버텍스 커버란 정점(Vertex)들의 집합으로, 주어진 그래프에서 버텍스 커버에 포함된 정점들을 제거하면 간선이 하나도 남지 않게 되는 집합을 말한다. 최소 버텍스 커버는 이와 같은 집합들 중 크기(정점의 개수)가 최소인 것을 말한다.

그래프에서 정점을 제거할 때는, 그 정점에 연결된 모든 간선도 함께 제거하게 된다.

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

둘째 줄부터 N개의 줄에 A_i와 연결되어 있는 정점의 개수가 주어지고, 그 개수만큼 B_j의 j가 주어진다.

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

둘째 줄에는 A에서 최소 버텍스 커버에 포함되어 있는 정점의 개수를 출력하고, 포함되어 있는 정점의 번호(A_i에서 i)를 출력한다.

셋째 줄에는 B에서 최소 버텍스 커버에 포함되어 있는 정점의 개수를 출력하고, 포함되어 있는 정점의 번호(B_j에서 j)를 출력한다.