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?

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$
  

Example 1

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.