唔西·迪西和玛卡·巴卡到迷宫里探险，不了他们两错乱中竟然分散了，迷宫的大小为$N×M(2≤N≤300,2≤M≤300)$。
迷宫里有一些传送装置，可以将人从一点到另一点进行瞬间转移。这些装置可以双向使用。
如果莫个人处在这个装置的起点或者终点，那么就必须使用这个装置，在传送过后不会立刻进行第二次传送，即不会卡在传送装置的起点和终点之间来回传送。
现在唔西·迪西想要和玛卡·巴卡会和，他们俩商量好如果分散了，唔西·迪西将会留在原地，玛卡·巴卡会前去寻找她。
迷宫中的每个元素都由以下项目中的一项组成：
死路，由 # 表示，这些格子是不可以通过的。
空地，由 . 表示，可以简单的通过。
传送装置，每一对大写字母 A 到 Z 表示。
唔西·迪西的位置，由 = 表示。
玛卡·巴卡的位置， 由 @ 表示
玛卡·巴卡能在一格空地上可能存在的四个相邻的格子移动，花费 1 个单位时间。从装置的一个结点到另一个结点不花时间。
求玛卡·巴卡找到唔西·迪西的最短时间。