Shortest Path in a Security Building

You are tasked with securing a facility that consists of n layers connected by m corridors. Each corridor connects two different layers and the facility can be modeled as an undirected graph where each node represents a layer and each edge represents a corridor.

Your goal is to determine the shortest path (in terms of the number of corridors) from a starting layer s to a target layer t. If s = t, the answer should be 0. If no path exists between the two layers, output "NO PATH".

The number of corridors in the shortest path is given by: $$distance$$ which should be minimized using a Breadth-First Search (BFS) strategy.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains four integers: n m s t, where n is the number of layers, m is the number of corridors, s is the starting layer, and t is the target layer.
• Each of the next m lines contains two integers u v indicating that there is a corridor connecting layer u and layer v.

outputFormat

Output the minimum number of corridors that must be traversed to go from layer s to layer t via standard output (stdout). If no such path exists, output "NO PATH".

5 6 1 5
1 2
2 3
3 4
4 5
1 3
2 5

2