Minimum Subway Transfers

You are given a subway system consisting of several subway lines. Each line is represented by a sequence of station IDs. You can travel freely along a line without any transfers. A transfer occurs when you switch from one subway line to another. Given a starting station and a destination station, your task is to determine the minimum number of transfers required to reach the destination. If the destination is not reachable, you should output -1.

More formally, let \(S\) be the number of stations and \(L\) be the number of subway lines. Each subway line is described by a list of station IDs. A transfer between two lines is possible if there is at least one station that is common to both lines. The goal is to find the minimum number of transfers (i.e. switches between lines) required to travel from the starting station to the ending station.

For example, consider the case where the subway system has two lines: the first line covers stations [1, 2, 3] and the second line covers stations [3, 4, 5]. To travel from station 1 to station 5, one must use the first line from station 1 to station 3, and then transfer to the second line at station 3 to reach station 5. Hence, the minimum number of transfers is 1.

Note: When the starting station and the destination station lie on the same subway line, no transfer is needed (i.e. the answer is 0). Otherwise, you may need one or more transfers. If there is no possible route, output -1.

inputFormat

The input is read from standard input and has the following format:

T
S L
k1 s1 s2 ... sk1
k2 s1 s2 ... sk2
...
kL s1 s2 ... skL
start end
... (repeated T times)

Here:

• T is the number of test cases.
• For each test case, the first line contains two integers \(S\) and \(L\), where \(S\) is the total number of stations and \(L\) is the number of subway lines.
• Then for each of the next \(L\) lines, the first integer \(k_i\) represents the number of stations in the \(i\)-th subway line, followed by \(k_i\) integers representing the station IDs on that line.
• The next line contains two integers: the starting station and the destination station.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of transfers required to travel from the starting station to the destination station. If it is impossible to reach the destination, output -1.

## sample

4
5 2
3 1 2 3
3 3 4 5
1 5
5 3
3 1 2 3
3 3 4 5
2 6 7
1 6
6 2
4 1 2 3 6
3 3 4 5
1 5
7 2
4 1 2 3 4
3 5 6 7
1 7

1
-1
1
-1

</p>