BFS Shortest Path in an Undirected Graph

You are given an undirected graph with n nodes and m edges. Your task is to find the shortest path between two given nodes using the Breadth-First Search (BFS) algorithm. The graph is provided as a list of edges, where each edge connects two nodes.

If a path exists from the start node to the destination node, output its length. Otherwise, output -1 to indicate that no path exists.

The problem can be formalized as follows:

Given a graph \(G=(V,E)\) with \(|V|=n\) and a list of edges \(E\), find the shortest distance between nodes \(s\) and \(t\) using BFS. If \(s = t\), the distance is 0.

inputFormat

The input is given via stdin and has the following format:

T
n1 m1
u11 v11
u12 v12
... (m1 lines)
s1 t1
n2 m2
u21 v21
... (m2 lines)
s2 t2
...

Where:

• T is the number of test cases. (T ≥ 1)
• For each test case:
• n is the number of nodes (nodes are numbered from 0 to n-1).
• m is the number of edges.
• Next m lines each contain two integers u and v representing an undirected edge between nodes u and v.
• The last line of the test case contains two integers s and t representing the start and destination nodes.

outputFormat

For each test case, output a single line to stdout in the format:

Case X: Y

Where X is the test case number (starting from 1) and Y is the length of the shortest path from s to t. If no such path exists, Y should be -1.

## sample

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

Case 1: 2
Case 2: 2
Case 3: -1
Case 4: 0

</p>