CSES - HIIT Open 2019 - HIIT Speedrun
  • 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

Example 1


5 6
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.

Example 2


3 2
1 2
2 3



Explanation: Only one letter I is available, so you can't win the game.