Gather the Maps!

時間制限 : 8 sec, メモリ制限 : 65536 KB

Problem F: Gather the Maps!

はるか昔、八尾氏が残したとされる伝説の秘宝が八王子のどこかに眠っているという。 その在処を示すとされる宝の地図は、いくつかの断片に分割された状態で、八尾氏の n 人の子孫達によって受け継がれている。

今、八尾氏の子孫達は協力してその秘宝を手に入れようとしていた。 ところが、秘宝の在処を指し示す宝の地図の一部分だけでは秘宝を見つけることができない。 そこで、八尾氏の子孫達は全員で集まって地図を 1 ヶ所に集めようとした。 ところが、いざ実行に移そうとしてもなかなか予定が合わずに集まることができない。 しかしこの秘宝に関する情報は、一族において秘密裏に伝えられてきた貴重な情報である。 漏洩の危険性を考慮すると、公共の通信手段を用いて地図をやりとりすることなど問題外である。

そこで、子孫同士が直接会って地図を手渡すということを繰り返すことで、ある 1 人の子孫のところに地図を集めることにした。 なお、1 人が 1 日に会える人数に制限はないが、互いにスケジュールが空いていることが必要である。

あなたの仕事は、それぞれの子孫に対するスケジュールの空いている日のリストから、地図を集めるには最低で何日必要かを求めるプログラムを書くことである。

ちなみに、八尾氏一族の結束は非常に固い。 最終的に地図全体を手にした子孫が、他の子孫を裏切って秘宝を持ち逃げすれば、一族から制裁を受けることになる。その制裁はきわめて恐ろしいものであるため、実際にその子孫が秘宝を持ち逃げすることは事実上不可能である。

Input

入力は複数のデータセットからなる。

それぞれのデータセットは複数の行からなる。 その最初の行には、地図の断片を持った者の人数を表す整数 n (1 < n <= 50) が記述されている。 続く n 行には、それぞれの子孫のスケジュールが書かれている。 i 行目は i 人目の子孫のスケジュールが表しており、いくつかの整数が 1 文字のスペースを区切りとして書かれている。 最初の整数 fi (0 <= fi <= 30) は、その子孫のスケジュールが空いている日の日数を表す整数である。 続く fi 個の整数は、スケジュールが空いている日付を表す。 これらの日付は互いに異なり、全て 1 以上 30 以下である。

入力の最後に 0 のみを含んだ 1 行がある。

Output

各データセットに対して、1 つの整数を 1 行に出力せよ。 もし、30 日以内に地図を集めることができる場合は、地図を集めるのに最低限必要となる日数を、集めることができない場合は -1 を出力せよ。

追記 : 上記の「地図を集めるのに最低限必要となる日数」は 1 日を起点として最も早く全ての地図が集まる日付を意味する.

Sample Input

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

Output for the Sample Input

3

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2005, 2005-06-19
http://acm-icpc.aitea.net/