게임
시간 제한2초메모리 제한256 MB
각 팀원이 가진 힌트 집합이 주어질 때, 1팀의 각 선수가 2팀 선수 한 명에게만 없는 힌트 하나를 물어볼 수 있는 규칙에서 1팀이 모든 힌트를 반드시 모을 수 있는지 판정하고, 가능하면 배정을 출력한다.
문제
바이트랜디아의 국왕이 매년 지적 게임을 연다. 게임 규칙에 따라 모든 참가자는 두 팀으로 나뉘고, 각 선수는 힌트 집합을 받는다. 게임이 진행되는 동안 참가자들은 다음 규칙에 따라 힌트를 교환할 수 있다. 제1팀의 각 선수는 제2팀의 선수 한 명에게 다가가 아직 모르는 힌트를 요청할 수 있다. 그러한 힌트가 여러 개면 제2팀 선수는 그중 아무거나 하나를 알려준다. 제1팀의 각 선수는 제2팀 선수 한 명에게만 힌트를 물을 수 있고, 제2팀 선수 한 명에게 여러 선수가 요청할 수 있다. 제1팀이 모든 힌트를 모으면 승리한다. 제2팀의 답변과 무관하게 제1팀이 모든 힌트를 모을 수 있는지 팀장이 알아내도록 도와라.
입력
첫째 줄에 세 정수 n, m (1 ≤ n, m ≤ 500), k (1 ≤ k ≤ 5000)가 주어진다. 이는 각각 팀의 크기와 힌트의 개수다. 다음 n+m개 줄에는 게임 시작 시 선수들이 가진 힌트 정보가 다음 형식으로 주어진다. 줄의 첫 번째 수는 그 선수가 가진 힌트의 개수이고, 이어지는 수들은 힌트 번호로 k를 넘지 않는 자연수다.
출력
제1팀이 모든 힌트를 모을 수 있으면 첫째 줄에 1을 출력한다. 다음 줄에 n개의 수를 출력하는데, 제1팀의 각 선수가 어느 제2팀 선수에게 힌트를 요청해야 하는지 나타낸다. 답이 여러 개면 아무거나 출력한다. 제1팀이 모든 힌트를 모을 수 없으면 첫째 줄에 2만 출력한다.