小 I 和小 B 最近沉迷一款叫做《Project Summer》 的游戏, 小 I 扮演这个游戏中需要逃生的无辜者(Innocent), 小 B 扮演这个游戏中抓住无辜者, 阻止其逃生的背叛者(Betrayer)。
这个游戏的地图是一个 N 行 M 列 的矩形, 每个格点表示一个位置。
'#' 表示地图中的障碍物, '.' 表示地图中的空地, 此外, 地图中还有只有背叛者才能使用的传送门, 用小写字母 'a' - 'z' 标记, 它们在地图上成对出现。
角色可以花费 1 单位的时间从一个格子走到上下左右相邻的 4个空地中的另一个格子(不可以走出地图边界或者走到障碍物上)。此外, 当小 B 扮演的背叛者走到一个传送门上时, 他可以花费 1 单位的时间从当前格子传送到与当前格子相同字母的另一个传送门处(他也可以选择不传送, 此时没有花费任何时间, 待在原地不动)。
传送是双向的。 比如, 现在小 B 走到了标记为 'a' 的格子上, 那么他可以选择花费一单位的时间传送到另一个标记为 'a' 的格子上, 也可以选择不传送, 那么他就待在原地不动。
现在, 小 I 被小 B 的陷阱困住了, 无法移动。 给出地图上小 B 和小 I 所在的格子(他们都站在空地上), 求小 B 最少需要花费多少时间才能走到小 I 所在的格子抓住他。 如果小 I 无法抓住小 B, 输出 -1