PEG Test - December 2014

Problem A: Secret Santa

PEG is hosting its first annual Secret Santa! To preserve secrecy amongst the Santas, Alex numbers the N (1 ≤ N ≤ 30) PEG students from 1 to N. Their names will henceforth correspond to these numbers. In Secret Santa, everybody's name is placed into a hat. Alex carries the hat around the classroom, and each person draws a name from the hat that is guaranteed to not be their own. Each person keep their selection a secret, and must send a gift to that person later on.

Ben's job during the name draw was to follow Alex around and write down which person drew which person, in case anybody forgets their selection and later comes to ask. However, amidst all his university application papers, Ben has lost the sheet that recorded each person's selection. PEG members are naturally forgetful. As expected, a few days before the gifting and reveal, many students reported that they've forgotten the name of the person they've drawn. When all these people went to consult Ben, he became visibly distraught. Drastic action must be taken. So, Ben went around and secretly asked everybody to give a list of names of their possible partners.

Each person gives Ben a list of names of people that might be their partner. Clearly, for someone who remembers their partner's name, this list will contain exactly one name. For someone who haven't a clue who their partner is, this list will contain everybody's name. It is guaranteed that a person's list will contain their partner. Using these hints, Ben would like to determine one valid way to reassign names to those who have forgotten, such that everybody in PEG has a distinct secret Santa.

Input Format

Line 1 will contain a single integer N, specifying the number of students.
For the next N lines, each line will correspond to a student. More specifically, line i + 1 will describe the list of possible partners given by student i.
For each of these lines, the first number on the line will describe how many people are on the list, and then the actual list will follow on that line. For example, a line containing "4 10 11 12 13" means that the student's potential selection could've been either one of students 10, 11, 12, and 13.

Output Format

Output a single line containing N space-separated integers, describing the Secret Santa configuration. Student i (for 1 ≤ i ≤ N) is the secret Santa of the i-th integer on the line. It is guaranteed that a solution, although not necessarily unique, will exist. You may output any such solution.

Sample Input

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

Sample Output

2 3 1 5 4

Explanation

Student 1 knows for sure that his choice is student 2. Student 2 forgot whether he picked student 3 or 5. Student 3 knows for sure that he picked student 1. Student 4 completely forgot, so it could've been anybody of 1, 2, 3, or 5. Student 5 knows for sure that he picked student 4. In other words, we don't know the choices for students 2 or 4. We DO know that if 2 picked 3, then 4 must have picked 5, or if 2 picked 5, then 4 must have picked 3. So another valid answer is "2 5 1 3 4".

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 13, 2014
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)