ICPC 2002 Asia Regional - Taejon D번- 크리스마스 선물 > 문제은행 : 정보올림피아드&알고리즘




3550 : 크리스마스 선물

제한시간
3000 ms   
메모리제한
128 MB   
해결횟수
3 회   
시도횟수
11 회   

문제

매년 크리스마스가 되면 부모들은 아이들이 만족할 수 있도록 크리스마스 선물을 주기 위해 고민을 하게 된다. 특히 아이들은 다른 아이가 받은 선물을 보고 부러워할 수 있기 때문에, 남을 부러워하는 아이가 없도록 선물을 잘 선택해야 한다.

 

 올해도 어김없이 크리스마스가 왔기 때문에, 상수는 올해에도 까다로운 아이들에게 선물을 줘야 한다. 선물을 사러 가기 전에 상수는 아이들에게 선물 리스트를 보여준 뒤, 각 아이들에게 원하는 선물을 물어봤다. 아이들이 선물을 고르기만 하면 좋겠지만, 남이 가진 선물이 나한테 없다면 슬픈 아이들이 있을 것이라는 것 정도는 충분히 유추할 수 있을 것이다.

 

 까다로운 조사 끝에, 상수는 아이들의 요구들을 4가지 종류로 나눴다. 

 

종류 1. 선물 집합

종류 2. 특정 아이가 가지고 있는 선물 전체

종류 3. 종류 1 또는 종류 2에 해당하는 조건 2개의 “교집합”

종류 4. 특정 아이가 가지고 있는 선물 중, 특정 몇 가지를 제외한 것

 

 각 아이는 여러 가지의 요구를 동시에 할 수 있으며, 이 때 모든 요구 조건이 만족되어야 아이가 불평하지 않는다. 이 때 선물을 최소한으로 구매하여 모든 아이의 요구 조건을 만족시키는 선물 구매 목록을 출력하여라.

 

예를 들어, 세 아이 (정올, 수올, 물올)와 선물 (정보, 수학, 물리)에 대해서, 각 아이가 다음과 같은 요구를 했다고 하자.

 

 

  1. 정올은 {정보, 수학}과, {수올}과 {물올}이 가진 선물의 교집합을 원한다.
  2. 수올은 {물올이 가진 선물}과 {수학, 물리}의 교집합을 원한다.
  3. 물올은 {정보}와, {정올이 가진 선물}에서 {물리}를 뺀 것을 원한다.

 

 

정올에게 {정보, 수학}을, 수올에게 {수학}을, 물올에게 {정보, 수학}을 사주는 것이 최소이다.

 


입력형식

첫 줄에 선물의 가짓수 n과 사람 수 m이 주어진다. (1≤n≤1000, 1≤m≤100) 선물은 1부터 n까지의 번호가 매겨지며, 아이들은 1부터 m까지의 번호가 매겨진다.

 두 번째 줄부터, 각 아이의 요구 조건이 다음과 같은 형식으로 n번 주어진다.

 첫 번째 줄에는 아이의 번호와 요구 조건의 개수 k가 주어진다.

 그 이후, k개의 줄에 걸쳐 요구조건이 다음과 같은 형식으로 주어진다.

 

종류 1. 가장 처음에 -1이 입력으로 주어진다. 그 후, 선물 집합의 크기 s와, 선물의 종류를 나타내는 s개의 숫자가 주어진다. 예를 들어, 선물 집합이 {1, 2}인 경우 다음과 같이 주어진다.

 

-1 2 1 2

 

종류 2. 가장 처음에 -2가 입력으로 주어진다. 그 후, 특정 아이의 번호가 주어진다. 예를 들어, 2번 아이가 가진 선물을 가지고 싶은 경우 다음과 같이 주어진다.

 

-2 2

 

종류 3. 가장 처음에 -3이 입력으로 주어진다. 그 후, 종류 1이나 종류 2와 같은 형식으로 2개의 조건이 주어진다. 예를 들어, 3번 아이와 {2, 3}번 선물의 교집합을 원하는 경우는 다음과 같다.

 

-3 -2 3 -1 2 2 3

 

다른 예시로, 2번 아이와 3번 아이가 가진 선물의 교집합을 원하는 경우는 다음과 같다.

 

-3 -2 2 -2 3

 

종류 4. 가장 처음에 -4가 입력으로 주어진다. 그 후, 종류 2, 종류 1 순서로 주어진다. 예를 들어, 1번 아이가 가진 것 중 {3}번 선물을 제외한 선물을 가지고 싶은 경우는 다음과 같다.

 

-4 -2 1 -1 1 3

 


출력형식

m개의 줄에 각 아이가 받는 선물의 종류를 다음과 같이 출력한다.

i번째 줄에는 아이의 번호를 의미하는 i를 출력한 뒤, i번째 아이가 받는 선물을 오름차순으로 출력한다. 

만약 아이가 선물을 받지 않는다면, 그 줄에는 i만 출력될 것이다. 


입력 예

2 2
1 1
-1 1 1
2 1
-4 -2 1 -1 1 1

출력 예

1 1
2

입력 예

1 1
1 1
-3 -1 1 1 -1 1 1

출력 예

1 1

입력 예

3 3
1 2
-1 2 1 2
-3 -2 2 -2 3
2 1
-3 -2 3 -1 2 2 3
3 2
-1 1 1
-4 -2 1 -1 1 3

출력 예

1 1 2
2 2
3 1 2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP