Shortest Path in an Unweighted Graph

The city of Ninjaland is represented as an unweighted graph with houses and roads. There are 'N' houses numbered 1 to 'N', connected by 'M' bidirectional roads. A road connecting two houses 'X' and 'Y' allows travel in both directions (X to Y and Y to X). It is confirmed that every house can be reached from every other house via some combination of roads. Note that two houses are directly connected by at most one road.

You need to determine the shortest path from house 'S' to house 'T'. A path is a sequence of houses starting at 'S' and ending at 'T', with each consecutive pair of houses connected by a road.

Example:

Input:

N = 8, M = 9, S = 1, T = 8
Roads: (1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 8), (4, 7), (5, 8), (6, 7)

Output:

[1, 3, 8]

Explanation:

The shortest path from 1 to 8 is [1, 3, 8]. Other paths like [1, 2, 5, 8] or [1, 4, 6, 7, 8] exist but are longer.

Constraints:

• 1 <= T <= 100
• 2 <= N <= 10³
• 1 <= M <= min(N*(N - 1)/2, 1000)
• 1 <= S, T <= N
• Time Limit: 1 sec

Input:

The first line contains a single integer 'T', the number of test cases.
For each test case, the first line contains two integers 'N' and 'M'.
The second line contains two integers 'S' and 'T'.
The next 'M' lines each contain two integers 'X' and 'Y', representing a road between houses 'X' and 'Y'.

Output:

Return a list of house numbers indicating the shortest path from 'S' to 'T'.
If multiple shortest paths exist, return any one.
The result for each test case should be "Correct" if the output path is valid, otherwise "Incorrect".

Note:

You are only required to implement the function to find the path; output is handled elsewhere.