cho.sh연구초미니
문제 설명
시간 제한
메모리 제한
cho.sh시간 제한
메모리 제한
시간 제한
3초
메모리 제한
128 MB
매년 부모가 겪는 즐거운 골칫거리는 아이들에게 줄 크리스마스 선물을 준비하는 일이다. 아이들은 서로가 무엇을 받았는지 비교하기 때문에, 부모는 어느 아이도 다른 아이를 부러워하지 않도록 선물을 정해야 한다.
부모는 쇼핑을 가기 전에 정해진 선물 후보 집합을 아이들에게 알려 주고, 각 아이가 그 후보들의 부분집합을 받게 된다고 말한다. 그러면 각 아이는 자신이 만족하기 위한 조건을 부모에게 말한다. 각 아이의 조건은 형제자매가 받게 될 선물을 기준으로 상대적으로 표현된다. 부모의 목표는 모든 아이의 조건을 만족시키면서, 각 아이에게 주는 선물 집합을 가능한 한 작게 하는 것이다.
모든 조건은 다음과 같은 논리곱(그리고)으로 표현된다.
여기서 각 αi는 다음 중 하나이다.
"최소한 (α1 그리고 ... 그리고 αk) 만큼이 필요하다"는 것은 그 아이의 선물 집합이 모든 αi를 포함해야 한다는 뜻이므로, 조건을 만족하는 가장 작은 집합은 정확히 모든 αi의 합집합이다. αi가 다른 아이의 선물을 참조할 수 있으므로 각 집합은 서로 얽혀 정의된다. 모든 조건을 동시에 만족하는 가장 작은 배정을 구하면 되며, 그러한 배정은 항상 존재하고 유일하다.
예시. 세 아이 {X, Y, Z}와 세 선물 후보 {a, b, c}에 대해:
이때 각 아이에게 주는 가장 작은 선물은 X는 {a, b}, Y는 {b}, Z는 {a, b}이다.
입력은 T개의 테스트 케이스로 이루어진다. 첫 줄에 T가 주어진다. 선물 후보는 1부터 n까지 번호가 매겨진다 (1 ≤ n ≤ 1000). 아이들은 1부터 m까지 번호가 매겨진다 (1 ≤ m ≤ 100).
입력은 공백으로 구분된 정수들의 나열이며, 아래에서는 줄 단위로 설명한다.
각 아이의 조건은 다음과 같이 주어진다.
두 정수, 즉 아이의 식별 번호와 조건을 이루는 부분 αi의 개수가 있는 줄.
그다음 한 줄에 하나씩 부분 αi가 주어진다. 각 αi 줄은 유형을 나타내는 값으로 시작한다. 유형 1은 -1, 유형 2는 -2, 유형 3은 -3, 유형 4는 -4이다.
[유형 1] -1 다음에 개수 k와 k개의 정수가 와서 선물의 상수 집합을 나타낸다. 예를 들어 -1 2 1 2는 집합 {1, 2}를 나타낸다.
[유형 2] -2 다음에 형제자매의 식별 번호 하나가 온다. 예를 들어 -2 2는 형제자매 2의 선물을 나타낸다.
[유형 3] -3 다음에 유형 1 또는 유형 2 형식의 피연산자 두 개가 온다. 예를 들어 -3 -2 3 -1 2 2 3은 형제자매 3의 선물과 집합 {2, 3}의 교집합을 나타내고, -3 -2 2 -2 3은 형제자매 2와 형제자매 3의 선물의 교집합을 나타낸다.
[유형 4] -4 다음에 유형 2 피연산자와 유형 1 피연산자가 차례로 온다. 예를 들어 -4 -2 1 -1 1 3은 형제자매 1의 선물에서 {3}을 제외한 것을 나타낸다.
각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스에 대해, 아이의 식별 번호가 커지는 순서로 아이마다 한 줄씩 출력한다. 각 줄은 아이의 식별 번호로 시작하고, 그 뒤에 그 아이가 받는 선물 번호들을 커지는 순서로 출력한다. 선물을 받지 않는 아이는 식별 번호만 출력한다.