Shortest Path in a Maze

You are given a maze consisting of n rooms and m corridors. Each corridor connects two rooms bidirectionally. You are also provided with a starting room s and an exit room e. Your task is to determine the minimum number of corridors you must traverse to get from room s to room e. If room e is unreachable from room s, output -1.

The distance, denoted by \(d\), is defined as the minimum number of corridors traversed to reach the exit:

[ d = \min_{\text{paths } s\to e} (\text{number of corridors}) ]

If \(s = e\), then \(d = 0\).

inputFormat

The input is read from stdin and has the following format:

• The first line contains four integers: n m e s, where n is the number of rooms, m is the number of corridors, e is the exit room's id, and s is the starting room's id.
• The next m lines each contain two integers u and v, representing a corridor connecting room u and room v.

outputFormat

Output a single integer to stdout that represents the minimum number of corridor traversals required to reach the exit room from the starting room. If the exit room is unreachable, output -1.

## sample

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

2

</p>