当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

水仙是春天的精灵，它们通过花粉在花园中悄然传播。在一个矩形花园里，已有一些水仙盛开（标记为 'S'），剩余的空地（标记为 '.'）等待绽放，而石头（标记为 '#'）会阻挡花粉的扩散。

每天黄昏，所有已盛开的花朵会向上下左右四个方向各释放一批花粉，若相邻格子是空地，则该空地次日也会盛开。花粉传播遵循以下规则：

• 花粉只能穿过空地，无法穿过石头；
• 传播是同步的，即所有花朵在同一天同时传播；
• 已盛开的花朵会持续盛开，不会再改变。

请你计算：至少需要多少天，整个花园中的所有空地都能盛开？如果存在某块空地永远无法被花粉到达（即被石头或边界隔离），请输出 -1。

输入格式

第一行包含两个整数 n, m（1 ≤ n, m ≤ 1000），分别表示花园的行数和列数。
接下来 n 行，每行一个长度为 m 的字符串，仅由以下字符组成：

• '.'：空地（尚未开花）
• '#'：石头（不可通行）
• 'S'：已盛开的水仙花

输入保证至少有一个 'S'。

输出格式

输出一个整数，表示使所有空地盛开所需的最少天数。若存在空地永远无法盛开，输出 -1。

样例1

输入

3 3
S..
...
..S

输出

2

解释：两个源分别位于 (0,0) 和 (2,2)。最远的空地是 (0,2) 或 (2,0)，距离最近源需要 2 步，因此答案为 2。

数据范围与约定

• 1 ≤ n, m ≤ 1000，网格总数不超过 10^6。
• 保证至少有一个 'S'。