Shortest Path to Treasure Room

You are given a dungeon consisting of n rooms (numbered 1 through n) and m bidirectional doors. Each door connects two different rooms. You are also given two special rooms: the starting room s and the treasure room t.

Your task is to compute the shortest path from s to t in terms of the number of rooms visited. You may assume that the doors allow travel in both directions. The problem can be mathematically formulated as finding a sequence of rooms \(r_1, r_2, \dots, r_k\) such that \(r_1 = s\), \(r_k = t\), and for each consecutive pair \( (r_i, r_{i+1}) \) there exists a door between them. The objective is to minimize \(k\), the number of rooms visited (including the start and treasure rooms).

Hint: A Breadth-First Search (BFS) algorithm is ideal for solving this problem efficiently.

inputFormat

The first line of input contains four integers: n, m, s, and t, where n is the number of rooms, m is the number of doors, s is the starting room, and t is the treasure room. The following m lines each contain two integers u and v indicating that there is a door connecting room u and room v.

outputFormat

Output a single integer representing the number of rooms in the shortest path from room s to room t. If the treasure room is unreachable, output -1.## sample

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

3