22119_DependenciesamongJobs

As everybody knows, our staffs need to do a lot of jobs to prepare for ZQUCPC. But I bet you can not image how terrible to arrange the jobs. We know, sometimes there are dependencies among the jobs. We say job 2 depends on job 1 that means before starting job 1 we must finish job 2. We assume that there is only one job processing in one moment, and any job is dependent on no more than ten jobs.

When we make up a jobs’ schedule, we should check whether it is valid. Now, your task is to find out the earliest finish time of some jobs.

Input will contain several test cases. The first line of each test case contains two integer numbers N ( 0 <= N <= 10,000 ) and M. The jobs are numbered from 1 to N. You need to calculate the earliest finish time of the job M. And then, the following N lines describe jobs. The first line is corresponding the job 1, second line is corresponding the job 2 and so on.

Each job’s describing line contains several positive integer numbers. The numbers are separated by spaces. The first one of the ith line shows the time ( <= 100 ) that ith job cost. The rest of numbers of the ith line are the jobs on which the job I depends.

N=0 indicate the end of input file. We guaranteed there is no circle on dependency.

2 2

3

2 1

3 3

3

2 1

4 1 2

0

5

9