Problem Statement
You are lost in a maze. After exploring the maze for multiple hours, you have mapped out the entire structure of the maze on paper. However, you are still unable to find the path to the exit.
Given the map of the maze, find the best path to exit the maze as quickly as possible. When exploring multiple paths from a junction, always explore the path to the node with the lower index first.
Output the concatenation of the indices of the junction nodes that lie on the path from the start to the end, in that order.
Terminologies
Junction
A junction point in a maze is a point where you have more than one way to go and have to make a decision on which way to go to. It is represented as a node Ni. The following images are examples of junctions in mazes.

Edge
An edge is a path from one junction node to another junction node. Formally, an edge e ∈ E is a set of two nodes Ni and Nj, such that i ≠ j and it is physically possible for you to travel from the junction node Ni to Nj or vice-versa without having to make any decisions in between.
{Ni, Nj} ∈ E ⟹ {Nj, Ni} ∈ E
Input Format
The first line of input contains a single integer t, which is the number of test cases. t test cases follow.
Each test case has multiple lines of input:
- The first line contains two space-separated integers, n and a.
- n is the number of junction points in the maze.
- a is the number of edges.
- The next a lines each contain two integers x and y, which denote an edge between x and y.
Constraints
- 1 ≤ t ≤ 102
- 1 ≤ n ≤ 102
- 1 ≤ a ≤ n × (n−1)/2
- 1 ≤ xi, yi ≤ n for all i ∈ [1, a]
- xi ≠ yi for all i ∈ [1, a]
Output Format
For each test case, output a single line of space-separated integers representing the junction numbers on the shortest path from the start to the exit. Assume that 1 is the start node, and n is the exit node. If two paths are the shortest path, print the one that chooses the lower index node at the first point of mismatch. If no path exists from start to exit, print -1.
Sample Input
2 6 8
1 2
1 4
2 3
2 4
3 4
3 5
4 6
5 6
7 8
1 2
1 4
2 3
2 4
3 4
3 5
4 6
5 6
Sample Output
1 4 6 -1
Explanation
- In the first test case, the shortest path from junction 1 to junction 6 is through junction 4. The output is "1 4 6".
- In the second test case, there is no path from junction 1 to junction 7. Hence, the output is "-1".
Solution
# Import necessary modules
from collections import deque, defaultdict
# Function to find the shortest path from node 1 to node n using BFS
def bfs_shortest_path(n, graph):
# Initialize visited list to keep track of visited nodes (1-indexed)
visited = [False] * (n + 1)
# Initialize prev list to reconstruct the path, set all to -1 initially
prev = [-1] * (n + 1)
# Initialize the queue with the starting node (node 1)
queue = deque([1])
# Mark the starting node as visited
visited[1] = True
# BFS loop to explore the graph level by level
while queue:
# Pop the node from the front of the queue
node = queue.popleft()
# If the target node `n` is reached, reconstruct the path from `n` to `1`
if node == n:
path = []
while node != -1:
path.append(node) # Append the current node to the path
node = prev[node] # Move to the previous node in the path
return path[::-1] # Return the path in the correct order (1 to n)
# Explore all neighbors of the current node, sorted to ensure lexicographically smallest path
for neighbor in sorted(graph[node]):
# If the neighbor has not been visited, process it
if not visited[neighbor]:
visited[neighbor] = True # Mark the neighbor as visited
prev[neighbor] = node # Set the current node as the predecessor of the neighbor
queue.append(neighbor) # Add the neighbor to the queue for further exploration
# If there's no path from node 1 to node n, return [-1] indicating no path found
return [-1]
# Function to handle multiple test cases and provide results
def solve(test_cases):
# Initialize a list to store results for each test case
results = []
# Loop through each test case
for t in test_cases:
n, a, edges = t # Unpack the number of nodes, number of edges, and the edges list
# Create a graph representation using a dictionary of lists
graph = defaultdict(list)
# Populate the graph with bidirectional edges
for x, y in edges:
graph[x].append(y) # Add edge from x to y
graph[y].append(x) # Add edge from y to x (undirected graph)
# Find the shortest path from node 1 to node n
path = bfs_shortest_path(n, graph)
# If no valid path is found, append "-1" to results
if path == [-1]:
results.append("-1")
else:
# If a valid path is found, convert it to a space-separated string and append to results
results.append(" ".join(map(str, path)))
# Print all results, each on a new line
print("\n".join(results))
# Input handling
t = int(input().strip()) # Read number of test cases
test_cases = [] # Initialize list to store all test cases
# Loop to read each test case
for _ in range(t):
n, a = map(int, input().strip().split()) # Read the number of nodes and edges
edges = [tuple(map(int, input().strip().split())) for _ in range(a)] # Read all edges
test_cases.append((n, a, edges)) # Store the test case in the list
# Call the solve function with all test cases
solve(test_cases)
Sample Solution Provided by Instructor
from collections import defaultdict
def bfs(n, adList):
# Initialize the open list with a tuple (node, parent). Start with node 1 and a parent of 0.
open = [(1, 0)]
# Dictionary to track parents of each node visited in the BFS.
parents = {0: 0} # Start with a dummy parent for 0, which doesn't exist.
while open:
# Dequeue the first element in the open list (FIFO for BFS).
node, parent = open.pop(0)
# If the node has already been visited, skip it.
if node in parents:
continue
# Record the parent of the current node.
parents[node] = parent
# Check if we have reached the target node 'n'.
if node == n:
# Reconstruct the path from node 'n' back to the root node '1'.
path = []
while node:
path.append(node)
node, parent = parent, parents[parent]
# Return the path from root to target node, reversing the order.
return path[::-1]
# Add all unvisited children of the current node to the open list.
for child in sorted(adList[node]):
if child not in parents:
open.append((child, node))
# If the loop exits without finding the target node, return [-1].
return [-1]
# Read the number of test cases.
t = int(input())
# Loop through each test case.
for _ in range(t):
n, a = map(int, input().split()) # Read the target node and the number of edges.
# Initialize the adjacency list using defaultdict of lists.
adList = defaultdict(list)
# Read the edges and populate the adjacency list.
for _ in range(a):
x, y = map(int, input().split())
adList[x].append(y)
adList[y].append(x) # Because the graph is undirected, add both directions.
# Call the bfs function to find the path from node 1 to node 'n'.
path = bfs(n, adList)
# Print the path (or -1 if no path was found).
print(*path)