- Time limit: 1.00 s
- Memory limit: 512 MB
Your task is to move from room $1$ to room $n$ and collect one letter H, two letters I and one letter T during your journey. You can collect the letters in any order. What is the minimum length of such a path?
Input
The first input line has two integers $n$ and $m$: the number of rooms and tunnels. The rooms are numbered $1,2,\dots,n$.
The second line has $n$ characters $c_1 c_2 \dots c_n$: the letter (A–Z) in each room.
Finally, there are $m$ lines that describe the tunnels. Each line has two integers $a$ and $b$: there is a tunnel between rooms $a$ and $b$.
Output
Print one integer: the minimum length of a valid path from room $1$ to room $n$. If there is no such path, print "IMPOSSIBLE".
Constraints
- $1 \le n \le 100$
- $0 \le m \le 5000$
Input:
5 6
ITHXI
1 2
1 3
1 4
3 4
3 5
4 5
Output:
4
Explanation: An optimal path is $1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5$.
Example 2
Input:
3 2
HIT
1 2
2 3
Output:
IMPOSSIBLE
Explanation: Only one letter I is available, so you can't win the game.