算法设计与分析

闺蜜的八卦路径

动态规划典型题(3)- 闺蜜的八卦路径

Description

我们都知道八卦的传播是迅速的。当一个人知道一条八卦时,她会告诉所有她的所有闺蜜。

假设一个人告诉所有闺蜜需要单位时间,那所有人都知道这条八卦需要多少时间呢?

我们关心的问题当然不止这些,我们希望得到八卦的“中心”在哪里,也就是说,谁最先知道八卦从而使所有人知道八卦的时间最短?

Input

多组输入样例。每组case:

第一行一个整数n,代表人数。

接下来有n行,对于其中的第i行:

第一个数(k_i)代表第i个人的闺蜜数。

接下来2*k_i个数,分别代表其闺蜜的编号和传播八卦的时间。

输入以一组n=0的数据结束,且该数据无需处理。

Output

对于每组数据:

如果能使所有人都收到这条八卦,输出最快的起始传播点(如果有多个输出编号最小的)和对应的时间。否则输出“disjoint”。

Sample Input

3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 0 2 2 5 1 5 0

Sample Output

3 2 3 10