Gather the Maps!
InterviewTime limit8sMemory limit512 MB
Each person is free on some subset of days 1 to 30; find the earliest day by which repeated pairwise meetings can collect all map fragments at one person.
- Level
Medium6 of 10
- Topics
- Graph, BFS, Bit manipulation, Implementation
- Solved
- No attempts yet
Problem
Long ago, a legendary treasure said to have been left behind by Yao is said to lie somewhere in Hachioji. The treasure map that reveals its location has been divided into several fragments, passed down among Yao's n descendants.
Yao's descendants were now working together to obtain the treasure. However, a fragment of the treasure map alone cannot locate the treasure. So all of Yao's descendants tried to gather the map in one place. But when it came time to actually do it, their schedules rarely matched and they could not meet. Yet the information about this treasure is precious, secretly passed down within the family. Considering the risk of leakage, exchanging the map through public communication is out of the question.
Thus, they decided to have descendants meet in person and hand over the map repeatedly, gathering the map at one descendant's location. A person can meet any number of people in a day, but they must both be free on that day.
Your job is to write a program that, given each descendant's list of free days, finds the minimum number of days needed to gather the maps.
Incidentally, the Yao family's bond is very strong. If the descendant who ends up holding the entire map betrays the others and runs off with the treasure, they will face the family's punishment. That punishment is so terrible that it is effectively impossible for that descendant to actually run off with the treasure.
Input
The input consists of multiple datasets.
Each dataset consists of several lines. The first line contains an integer n (1 < n ≤ 50), the number of people holding map fragments. The following n lines describe each descendant's schedule. The i-th line describes the schedule of the i-th descendant, containing several integers separated by single spaces. The first integer f_i (0 ≤ f_i ≤ 30) is the number of days on which that descendant is free. The following f_i integers are the dates on which they are free. These dates are all distinct and are between 1 and 30 inclusive.
The input ends with a line containing only 0.
Output
For each dataset, output a single integer on one line. If the maps can be gathered within 30 days, output the minimum number of days needed to gather them; if not, output -1.
Note: The "minimum number of days needed to gather the maps" above means the earliest date, counting day 1 as the start, on which all maps are gathered.