PKU 1904. King's Quest

왕의 부탁

Time Limit: 15000MS	Memory Limit: 65536K
Total Submissions: 1493	Accepted: 494
Case Time Limit: 2000MS

설명

옛날 옛적에 N 명의 아들들이 있는 왕이 있었습니다. 또한 왕궁에는 N명의 아름다운 소녀들이 있었고 N 명의 아들들이 그 소녀들을 좋아한다는 것을 왕이 알아챘습니다. 그러나 왕의 아들들은 젊고 무뇌였기에 한 아들이 여러 명의 소녀를 좋아하는 경우도 있었습니다.

그래서 왕은 마법사에게, 그의 아들들이 각자가 원하는 소녀와 결혼할 수 있도록 하라고 시켰습니다. 그리고 마법사는 그 일을 해내어서 각 왕자가, 결혼하기를 원하는 소녀를 골랐는데, 당연하게도 일부일처제의 방식이었습니다.

그러나 왕은 그 결과를 보고 말하기를 "자네가 처리한 일의 방식이 마음에 들지만, 아직 만족스럽지 못하다네. 나는 각 아들이 결혼하기를 원하는 소녀들을 전부 알고 싶네. 당연하게도, 한 녀석이 결혼 상대로 원하는 여자들 중 한 명을 고른 뒤에는, 다른 아들녀석들이 자신이 원하는 상대가 남아있어서, 그 상대를 고를 수 있도록 자네가 해야 할 것이네."

왕이 원하는 방법은 마법사가 해결하기엔 너무 힘든 것이었습니다. 이제 당신은 마법사의 목숨을 구하기 위해 문제를 풀어야 합니다.

입력

첫 번째 줄은 왕의 아들들의 총 수인 N (1 <= N <= 2000) 입니다. 그 다음 N 개의 줄은 각 왕자가 좋아하는 소녀들의 목록(!)을 나타냅니다: 각 줄의 첫 번째로 나오는 Ki 는 각 왕자가 좋아하는 소녀들의 수이고 그 다음에 나오는 Ki 개의 서로 다른 정수들은 1 부터 N 까지의 소녀들의 번호(!)를 나타냅니다. 모든 Ki 의 총 합은 200000을 초과하지 않습니다.

각 케이스의 마지막 줄은 마법사가 만들었던 원래의 결과물로, N 개의 서로 다른 정수들인데, 그 결과에 따른다면 일부일처제가 강요된, 각 왕자들과 결혼하게 될 소녀들의 번호를 나타냅니다. 이 결과물은 결과적으로 옳은 결정들 중 하나인데, 왜냐하면 이 결과물 역시 각 왕자가, 좋아하는 소녀들중 한 명과 결혼하도록 만들어졌기 때문입니다.

출력

출력은 N 개의 줄로 나옵니다. 출력은 각 왕자가,  자신의 결혼이 끝난 뒤에 다른 왕자들의 결혼 역시 가능한, 고를 수 있는 소녀들의 총 수를 나타내는 Li 로 시작합니다. 그 뒤에 나오는 Li는 오름차순으로 그 번호를 나타냅니다.

입력 예시

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

출력 예시

2 1 2
2 1 2
1 3
1 4

힌트

이 문제는 입/출력할 데이터가 매우 크므로 TLE를 피하려면 cin과 cout로 데이터를 읽는 대신 scanf()와 printf()를 사용하세요.

Source

Northeastern Europe 2003

p.s: 해석이 매우 부자연스럽습니다. 미천한 제 실력을 탓하시고 절 채찍질하셔도 좋아요 (..)
p.s2: 어째서 힌트에 써있는게 권유형이 아닌 명령형이었을까요
p.s3: 힌트.. 라고 적혀있는 부분, 해석 안해야 할까요 앞으로?
p.s4: 난 하렘물은 싫어해요. 절대 내가 좋아서 고른 문제가 아닙니다. 로리라면 좋아하지만.. (응?)