Problem Description

Find the shortest path in a maze containing teleportation portals. The maze has walls (#), open paths (.), start (S), end (E), and portals marked with letters (A-Z). Portals with the same letter are connected bidirectionally and allow instant teleportation.

Input Format

First line contains m and n (maze dimensions). Next m lines contain the maze layout with characters: # (wall), . (path), S (start), E (end), A-Z (portals).

Output Format

Single integer representing the minimum steps to reach from S to E, or -1 if impossible.

Constraints

• 1 ≤ m, n ≤ 50

• Exactly one S (start) and one E (end)

• Portal pairs (same letter) can be 0 or more

• Teleportation through portals takes 0 additional steps

• Movement to adjacent cells takes 1 step

• Can move in 4 directions (up, down, left, right)

Sample Input/Output

4 5
S.#.E
..#..
A.#.B
A...B

4

Explanation

Path: S→(0,1)→A(2,0)→teleport to A(3,0)→(3,1)→(3,2)→(3,3)→B(3,4)→teleport to B(2,4)→E(0,4). Total steps: 4 (teleportation is free).