## TLE '16 Contest 3 P3 - Mysterious Package

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Authors:
Problem type
The not-so-mysterious mysterious package.

The CS Nerd has a mysterious package that he wants to deliver to the girl at school.

There are different classes occurring, the class occurs during period and has students in it. Two classes and occur at the same time if . Also, a class occurs later than another class if . Each student is assigned a unique, positive integer as an ID.

In order to pass the package to the girl, the person who currently has the mysterious package can pass the package to another student in the same class or hold on to the package to pass on in future classes.

However, the CS Nerd is incredibly suspicious of people and would like to minimize the number of passes made in order to complete the transaction (note that giving the package to the girl also counts as one pass). He would also like for the package to be delivered to the girl as early as possible, but he prioritizes a minimal number of passes. Can you help him determine the minimum number of passes necessary and the earliest possible period when the girl will receive the package?

#### Input Specification

The first line of input will contain .

The next line of input will contain two space-separated integers, the IDs of the CS nerd and the girl, respectively. It is guaranteed that these two IDs will appear in at least one class.

blocks of input follow; each block represents one class.

The first line of the block contains two space-separated integers, and .

The next line of the block will contain integers representing the IDs of students in the class. It is guaranteed that all IDs are in the range , that no student will be listed twice in the same class, and that no student has more than class with the same value of .

#### Output Specification

On separate lines, output two integers. The first integer will be the number of passes required to deliver the package by the end of the day. The second integer will be earliest possible period in which the girl receives the package if a minimal number of passes occurs.

If the girl cannot receive the package, output delivery failure instead.

#### Sample Input 1

6
1 10
1 3
16 2 1
3 3
7 10 2
1 3
52 7 14
2 3
16 10 52
2 2
14 4
1 2
10 4

#### Sample Output 1

2
2

#### Explanation for Sample Output 1

The CS Nerd (student ) can pass the package to student during class , who can in turn pass the package to the girl (student ) during class . This requires passes and the girl will receive the package during period .

#### Sample Input 2

3
30 5
1 5
6 30 10 1 42
2 3
5 8 29
1 4
29 31 2 8

#### Sample Output 2

delivery failure