题目描述

程老师承包了一片果园做病害观测。果园是 $n$ 行 $m$ 列的网格，每个格子要么是空地 .，要么是防风林 #，要么是消毒带 @，要么是初始病源 X。空地稀疏，防风林成排，消毒带是果园里预先划出的隔离区。

病害按天扩散。第 $d$ 天，所有"当前扩散源"格子同时把病害传给与它有公共边的相邻格子中尚未被感染的可感染格。空地和防风林都会被感染，消毒带永远不会被感染，也永远不会向外传播病害。

一个格子被感染的那一天记为它的感染日。初始病源在第 $0$ 天被感染。设某格在第 $d$ 天被感染，那么：若它是空地，它在第 $d+1$ 天成为扩散源；若它是防风林，被感染后还要花一天消化，它在第 $d+2$ 天才能成为扩散源。由此，初始病源在第 $1$ 天起就是扩散源。

程老师想知道，果园里所有可感染格（也就是所有不是消毒带的格子）全部被感染需要多少天，即最晚被感染格子的感染日。如果存在某个可感染格被消毒带挡住、永远无法被感染，请输出 -1。

输入格式

从文件 blight.in 中读入数据。

第一行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，仅含 .、#、@、X 四种字符，描述果园的一行。保证至少有一个 X。

输出格式

输出到文件 blight.out 中。

一行一个整数，表示所有可感染格全部被感染所需的天数；若存在永远无法被感染的可感染格，输出 -1。

数据范围

特殊性质 A：果园里没有 #。

特殊性质 B：果园里没有 @。

对于所有测试点：$1 \le n, m \le 1000$。

3 3
X#.
#..
..@

4

3 3
X@.
@..
...

-1

样例解释

样例 1：记第 $1$ 行第 $1$ 列的格子为 $(1,1)$，其余类推。

• 第 $0$ 天：只有 $(1,1)$ 被感染，它在第 $1$ 天起可以扩散。
• 第 $1$ 天：$(1,1)$ 把病害传给 $(1,2)$ 和 $(2,1)$，这两格都是防风林。
• 第 $2$ 天：$(1,2)$ 和 $(2,1)$ 都在消化，这一天没有新格子被感染。
• 第 $3$ 天：$(1,2)$ 和 $(2,1)$ 同时成为扩散源，$(1,3)$、$(2,2)$、$(3,1)$ 被感染。
• 第 $4$ 天：$(1,3)$、$(2,2)$、$(3,1)$ 向外扩散，$(2,3)$ 与 $(3,2)$ 被感染。

$(3,3)$ 是消毒带，不属于可感染格，不计入。最晚的感染日是 $4$，所以答案是 4。注意第 $2$ 天没有任何格子被感染，这一天是两格防风林在消化。

样例 2：$(1,1)$ 的病源要到第 $1$ 天才扩散，而它的两个相邻格 $(1,2)$、$(2,1)$ 都是消毒带，传不出去；剩下的空地既不是病源也不会凭空出现病害，永远无法被感染，所以输出 -1。