최소 k-커버링

이분 그래프 G = (U, V, E)가 주어진다. U는 첫 번째 파트의 정점 집합이고, V는 두 번째 파트의 정점 집합이며, E는 간선 집합이다. 다중 간선이 존재할 수 있다.

그래프 의 각 정점에 적어도 k개의 간선이 접할 때, 그리고 그럴 때에만 이 그래프의 어떤 간선 부분집합 을 k-커버링이라고 하자. 최소 k-커버링은 부분집합 의 크기가 가능한 한 최소인 k-커버링이다.

각 에 대해 최소 k-커버링을 찾아야 한다. 여기서 minDegree는 그래프 G의 모든 정점 중 최소 차수이다.

첫 번째 줄에 세 정수 n1, n2, m (1 ≤ n1, n2 ≤ 2000, 0 ≤ m ≤ 2000)이 주어진다. 이는 각각 첫 번째 파트의 정점 수, 두 번째 파트의 정점 수, 간선 수를 나타낸다.

이어지는 m개 줄 중 i-th 줄에는 i-th 간선을 설명하는 두 정수 ui와 vi (1 ≤ ui ≤ n1, 1 ≤ vi ≤ n2)이 주어진다. ui은 첫 번째 파트에 있는 정점의 인덱스이고, vi은 두 번째 파트에 있는 정점의 인덱스이다.

각 에 대해 간선의 부분집합(최소 k-커버링)을 별도의 줄에 출력한다.

k-th 줄의 첫 번째 정수 cntk는 그래프의 최소 k-커버링에 포함된 간선 수이다. 그 뒤에 cntk개의 정수가 주어져야 한다. 이들은 최소 k-커버링에 속하는 간선의 원래 인덱스이며, 서로 달라야 한다. 간선에는 입력으로 주어진 순서대로 1부터 m까지 번호가 매겨진다.