TLE '16 Contest 3 P3 - Mysterious Package

View as PDF

Submit solution

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

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 N different classes occurring, the i^{th} class occurs during period p_i and has s_i students in it. Two classes a and b occur at the same time if p_a = p_b. Also, a class x occurs later than another class y if p_x > p_y. 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 N (1 \leq N \leq 500).

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.

N blocks of input follow; each block represents one class.

The first line of the i^{th} block contains two space-separated integers, p_i (1 \leq p_i \leq 500) and s_i (1 \leq s_i \leq 500).

The next line of the i^{th} block will contain s_i integers representing the IDs of students in the i^{th} class. It is guaranteed that all IDs are in the range [1,10^9], that no student will be listed twice in the same class, and that no student has more than 1 class with the same value of p_i.

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

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


Explanation for Sample Output 1

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

Sample Input 2

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


There are no comments at the moment.