Shortest Friendship Path

Given a network of n people and m direct friendship connections, determine the minimum number of intermediate friends required to introduce two people, x and y. The friendship network is modeled as an undirected graph where each edge represents a direct friendship.

If x is already the same as y, the answer is 0. Otherwise, if there is a sequence of friendships connecting x to y, output the minimum number of direct friendship links required. If there is no such sequence, output IMPOSSIBLE.

You can represent the graph mathematically as follows: Given a graph \(G=(V,E)\) with \(|V| = n\) and \(|E| = m\), find the shortest path from vertex \(x\) to vertex \(y\). The length of the path is defined as the number of edges in the path.

inputFormat

The input is given from standard input (stdin) and has the following format:

n m
a1 b1
a2 b2
... (m lines total)
x y

Where:

• n is the number of people.
• m is the number of direct friendship connections.
• Each of the next m lines contains two integers ai and bi, indicating that person ai and person bi are direct friends.
• The last line contains two integers x and y, denoting the two people to be introduced.

outputFormat

Output a single line to standard output (stdout) that contains the minimum number of friendship connections required to introduce person x to person y. If it is impossible to connect x and y through the friendship network, output IMPOSSIBLE.

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

4