Shortest Path Length in an Undirected Graph

You are given an undirected graph represented as an adjacency list and two integers start and end. Your task is to compute the length of the shortest path between start and end using Breadth-First Search (BFS). If there is no path from start to end, output -1.

The graph is given in the following format:

• The first line contains two integers: start and end.
• The second line contains a single integer n representing the number of nodes in the graph. The nodes are numbered from 1 to n.
• The following n lines each describe the adjacency list for the i-th node. Each line begins with an integer k representing the number of neighbors, followed by k space-separated integers indicating the neighbors of node i.

Note: The graph is undirected, so if node u appears in the adjacency list of node v, then node v will also appear in the adjacency list of node u.

Formula: The length of the shortest path is the minimum number of edges connecting the start and end nodes. In LaTeX, this can be formulated as:
\( d(s,e) = \min \{ |P| : P \text{ is a path from } s \text{ to } e \} \)

inputFormat

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

start end
n
k1 neighbor1 neighbor2 ... neighbor_k1
k2 neighbor1 neighbor2 ... neighbor_k2
...
kn neighbor1 neighbor2 ... neighbor_kn

Where:

• start and end are the start and end nodes.
• n is the number of nodes.
• Each of the next n lines describes the neighbors of the i-th node. The first number in the line is the count of neighbors, followed by that many neighbor node identifiers.

outputFormat

Output a single integer to standard output (stdout): the length of the shortest path from start to end. If no such path exists, output -1.

## sample

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

2