Unweighted Graph Shortest Path Problem

You are tasked with finding the shortest path between two houses in the city of Ninjaland, represented as an unweighted graph. The city has N houses numbered from 1 to N and is connected by M bidirectional roads. Each road connects two houses, X and Y, allowing travel between them. It is guaranteed that every house is reachable from any other house.

Your goal is to determine the shortest path between two specified houses, S and T.

Example:

Input:

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

Output:

[1, 3, 8]

Explanation:

Multiple paths like (1, 2, 5, 8) or (1, 4, 6, 7, 8) exist but the shortest is (1, 3, 8).

Constraints:

• 1 ≤ T ≤ 100
• 2 ≤ N ≤ 103
• 1 ≤ M ≤ min(N * (N - 1) / 2, 1000)
• 1 ≤ S, T ≤ N
• Time Limit: 1 sec

Note:

You do not need to print anything; the function implementation takes care of it. Return the shortest path as a sequence of house numbers.