#P2326. ZY的密室

ZY的密室

即使ZY没有派出最强篮球阵容,机房篮球队还是暴虐了校篮球队。为了不打击校篮球队信心,ZY决定改变训练后的活动。近来,江大掌门的徒弟徒孙们纷纷事业有成,回到母校为机房捐钱捐物。财大气粗的机房组收回了五层六层的所有教室。ZY决定将六层的教室改造为智能密室逃脱活动室。

 

    每天傍晚,神牛们可以依次逐个进入游玩。我们简单的将教室分割为n*n个房间,K是你初始所在房间,T是你最终逃脱的房间。如果你想要逃脱房间,你必须依次找到m把钥匙。我们假定你从一个房间进入另一个房间需要花费1的时间。当然某些房间有些特殊的问题(地图上S表示)需要回答才能通过,对于机智的众牛们来说,这些问题根本不是问题。我们假定众牛们花费1的时间解决问题。(主要是出题的人表述不清,导致众牛理解困难;当然问题只需要回答一次,下次再次进入房间不需要回答了)

Input

多组文件输入,每个文件包含单个测试数据

第一行两个数字nm(0 < N <= 100, 0<=M<=9)

 

    接下来n*n描述地图

Output

需要最少时间逃脱密室。若无解输出impossible

Sample Input

3 1
K.S
##1
1#T
3 1
K#T
.S#
1#.
3 2
K#T
.S.
21.

Sample Output

5
impossible
8

HINT


要先取钥匙1,再取钥匙2。地图上可能有多个同一种钥匙,#为墙壁即不可走.

Source