Maze Path Finder

You are given an \(n \times n\) maze represented by a grid. Each cell in the maze is either 0 (open cell) or 1 (blocked cell). Your task is to find the shortest path from the top-left cell at \( (0,0) \) to the bottom-right cell at \( (n-1,n-1) \) using the Breadth-First Search (BFS) algorithm.

Details:

• Movement is allowed only in the four cardinal directions: up, down, left, and right.
• If a valid path exists, output the sequence of coordinates (each coordinate being a pair of row and column indices, 0-indexed) that form the shortest path from start to finish.
• If no valid path exists, print exactly No path exists.

Note: The maze provided as input is not guaranteed to have a valid path. In the case where no path is found, your program should output the string No path exists.

inputFormat

The first line contains a single integer \(n\) representing the number of rows (and columns) in the maze.

The following \(n\) lines each contain \(n\) space-separated integers (each either 0 or 1), representing the maze grid.

Example:

2
0 0
1 0

outputFormat

If a valid path exists, output the coordinates of each cell in the shortest path, one pair per line with the row index and column index separated by a space.

If no valid path exists, output the following:

No path exists

## sample

2
0 0
1 0

0 0
0 1
1 1

</p>