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