- Time limit: 1.00 s
- Memory limit: 512 MB
You are playing a game that consists of n rooms and m tunnels between them. Each room has a letter that you can collect.
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?
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.
Print one integer: the minimum length of a valid path from room 1 to room n. If there is no such path, print "IMPOSSIBLE".
- 1 \le n \le 100
- 0 \le m \le 5000
5 6 ITHXI 1 2 1 3 1 4 3 4 3 5 4 5
Explanation: An optimal path is 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5.
3 2 HIT 1 2 2 3
Explanation: Only one letter I is available, so you can't win the game.