Longest Subway Journey with Minimal Transfers

Johny is about to visit his friend Michelle by subway. Although he loves riding the subway and wants to spend as much time traveling as possible, his dad has imposed a restriction: he must change subway lines as few times as possible.

The subway system consists of several lines. Each line lists stations in the order the train stops. Trains on every line between two consecutive stations take exactly one minute and operate in both directions. Changing lines at a station (i.e. transferring from one line to another) takes no extra time.

Your task is to help Johny plan his trip from his starting station to Michelle's station so that the number of line transfers is minimized while the travel time (in minutes) is maximized among all such routes. Note that boarding the first line does not count as a transfer. A transfer is counted only when Johny switches from one line to another during his journey.

Important: Johny will not visit the same station twice during his trip.

The answer should output two integers: the minimal number of transfers and the maximum travel time (in minutes) possible under that minimal transfer constraint.

Input Format (detailed below):

inputFormat

The input begins with a line containing two integers S and T, representing Johny's starting station and Michelle's station respectively.

The second line contains a single integer L, the number of subway lines.

Each of the following L lines describes a subway line. Each line starts with an integer N which indicates the number of stations on that line, followed by N integers representing the station IDs in the order the train visits them.

outputFormat

Output two space‐separated integers on one line: the minimal number of transfers required and the maximum travel time (in minutes) among routes that achieve this minimal transfer count.

sample

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

0 3