P6096 [JSOI2015] Metro Lines

The subway in the JSOI Kingdom has become more expensive again. JYY, who is traveling in JSOI, is very unhappy. After this fare reform, passengers are not charged by travel distance, but by the number of transfers. JYY also needs to update his route search software accordingly. JYY thinks: if he pays the same fare, wouldn’t it be better for him if he can ride through more stations? So JYY wants to develop a route search program so that he can always “profit” the most. The JSOI subway has $N$ lines and $S$ stations. Line $i$ contains $L_i$ stations. Each subway line is a straight line from its starting station to its terminal station (there are no weird circular lines like Beijing Subway Line 2 or Line 10). Also, each line runs in both directions. If different lines pass through the same station, passengers can transfer at that station. Under the latest JSOI subway fare rule, every time a passenger enters a running subway train, they must pay a fee of $1$. Therefore, if a passenger transfers $x$ times in total, they need to pay $x+1$ fares. Since each line runs in both directions, at any station you may transfer to the opposite-direction train of the same line. Note that even transferring to the opposite direction of the same line still requires paying (because you always need to get off and then get on again). Now JYY wants to take the subway from station $A$ to station $B$. Assume that for any subway line, the travel time between two adjacent stations is $1$ minute, and stopping at stations and transferring both take no time. JYY wants to know: 1. The minimum fare he needs to pay. 2. Under the minimum fare, the maximum number of minutes he can spend riding the subway.

The first line contains two positive integers $N$ and $S$. The second line contains $S$ space-separated strings, the names of the $S$ stations. The next $N$ lines each describe one subway line. For line $i$, the line first contains a positive integer $L_i$, followed by $L_i$ strings, the station names on this line. A line is allowed to stop at the same station multiple times. Line $N+3$ contains two different strings $A$ and $B$, meaning JYY is currently at station $A$ and wants to go to station $B$.

The first line contains an integer $C$, the minimum fare JYY needs to pay. The second line contains an integer $T$, the longest time he can ride the subway while spending $C$. If there is no route between the two stations, output `-1` on the first line and `0` on the second line.

For $100\%$ of the testdata, $2\leq N\leq 4\times 10^5$, $S\leq 3\times 10^5$, $\sum L_i\leq 8\times 10^5$. It is guaranteed that the length of every input string does not exceed $40$, and each string contains only letters, digits, and hyphen `-`. Translated by ChatGPT 5