cho.shSCCC 신입 부원 모집하기
아직 제출이 없습니다시간 제한2초메모리 제한1024 MB문제
SCCC의 회장인 찬솔이는 2023년 1학기 신입 부원 선발 과정을 진행하고 있다. SCCC는 2023년 1학기에 정원이 X명인 스터디 그룹을 K개 운영하고, 이번 학기에 새로 들어오는 신입 부원들은 K개의 스터디 그룹 중 정확히 하나의 그룹에 참가해야 한다. 참가할 수 있는 스터디 그룹이 없으면 합격할 수 없으므로 모든 지원자는 본인이 참가할 수 있는 스터디 그룹을 한 개 이상 선택했다.
찬솔이는 공정하고 엄격한 심사를 통해 N명의 지원자들에게 서로 다른 점수를 매겼다. 이제 신입 부원들을 스터디에 배정하기 위해 점수가 높은 사람에서 낮은 사람 순으로 정렬한 다음, 한 명씩 스터디 그룹에 배정하려고 한다.
구체적으로, 점수가 i번째로 높은 사람을 스터디 그룹에 배정하려고 하는 상황을 생각해 보자. 만약 지금까지 스터디에 배정된 사람들의 집합을 유지하면서 i번째 사람을 스터디에 넣을 수 있으면 i번째 사람을 스터디에 배정한다. 반대로, 지금까지 스터디에 배정된 사람들을 어떻게 이동시키더라도 i번째 사람이 들어갈 수 있는 자리가 없다면 i번째 사람을 스터디에 배정될 수 없다.
예를 들어 N=5,K=2,X=2이고, 점수가 높은 사람부터 각 지원자가 참가할 수 있는 스터디 그룹이 1,1,2,1,1,2라고 하자.
점수가 가장 높은 사람과 두 번째로 높은 사람이 모두 1번 그룹에 배정되었고, 세 번째로 높은 사람을 배정해야 하는 상황을 생각해 보자. 두 번째 사람의 스터디 그룹을 2번 그룹으로 옮긴 뒤 세 번째 사람을 1번 그룹에 배정하면, 이전까지 스터디에 배정된 사람들의 집합을 유지하면서 세 번째 사람을 스터디에 넣을 수 있다.
반면, 1번 그룹에 첫 번째와 세 번째 사람, 2번 그룹에 두 번째 사람이 배정된 상황에서 네 번째 사람을 배정할 방법은 존재하지 않는다. 하지만 점수가 가장 낮은 사람은 2번 그룹에 들어갈 수 있으므로 최종 결과는 1번 그룹에 첫 번째와 세 번째 사람, 2번 그룹에 두 번째 사람과 다섯 번째 사람이 배정되는 것이다.
찬솔이는 이 규칙에 따라 지원자들을 스터디 그룹에 배정하려고 한다. 이때 스터디 그룹에 배정되는 사람의 수와, 각 스터디 그룹에 배정된 지원된 사람의 목록을 구해야 한다. 신입 부원 선발 외에도 많은 일을 처리해야 하는 찬솔이를 위해 스터디 배정 프로그램을 대신 작성해 주자.
입력
첫째 줄에 지원자 수 N, 스터디 그룹의 개수 K, 각 스터디 그룹의 정원 X가 공백으로 구분되어 주어진다.
둘째 줄부터 N개의 줄에 걸쳐, i번째 줄에 i번째 지원자의 정보가 주어진다. (1≤i≤N)
지원자의 정보는 한 줄로 구성되어 있다. 각 줄의 처음에는 참가할 수 있는 스터디의 개수 C_i가 주어지고, 이어서 참가할 수 있는 C_i개의 스터디 그룹의 번호 A_i,1,A_i,2,⋯,A_i,C_i가 공백으로 구분되어 주어진다.
N+2번째 줄에는 각 학생의 점수 B_1,B_2,⋯,B_N이 공백으로 구분되어 주어진다.
출력
첫째 줄부터 K개의 줄에 걸쳐, i번째 줄에 i번 그룹에 배정된 사람의 정보를 출력한다. (1≤i≤K)
각 줄의 처음에는 해당 스터디 그룹에 배정된 사람의 수, 그리고 이어서 배정된 사람의 번호를 공백으로 구분하여 출력한다.
답이 여러 개 존재하면 아무거나 출력해도 되며, 배정된 사람의 번호를 출력하는 순서는 무관하다.
제한
- 1≤N,K,X≤15
- 1≤K×X≤15
- 1≤C_i≤K
- 1≤A_i,j≤K (1≤i≤N,1≤j≤C_i)
- j=k 이면 A_i,j=A_i,k이다. (1≤i≤N,1≤j,k≤C_i) 즉, 각 행의 원소는 모두 서로 다르다.
- 1≤B_i≤109 (1≤i≤N)
- i=j 이면 B_i=B_j이다. (1≤i,j≤N) 즉, B의 원소는 모두 서로 다르다.
- 입력으로 주어지는 수는 모두 정수이다.