• 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.