第一部分：背景知识讲解

1. 赤壁之战与连环船

东汉末年，曹操将战船用铁索相连，形成“连环船”。虽然解决了北方士兵晕船的问题，但也导致船体无法灵活机动。一旦某处起火，火势会顺着连接的战船迅速向四周蔓延。

2. 算法模型：BFS (广度优先搜索)

火势蔓延是一个典型的由近及远、层层扩散的过程。

• $T=0$：起火点燃烧。
• $T=1$：距离起火点 1 步的船燃烧。
• $T=2$：距离起火点 2 步的船燃烧。 ...
• $T=K$：距离起火点 $K$ 步的船燃烧。

这种“求最短时间”或“求最少步数”的问题，是 BFS (Breadth-First Search) 的绝对主场。

第二部分：题目内容

题目名称：火烧连营 (Fire at Red Cliffs)

题目描述

曹操的铁索连环船阵可以看作一个 $N$ 行 $M$ 列的二维网格。 网格中的每个字符代表该位置的状态：

• .：代表江水。火无法在江水上蔓延，且无法穿过江水引燃另一侧的船。
• #：代表普通战船。一旦相邻（上下左右）的位置有火，下一秒它就会被引燃。
• F：代表起火点（黄盖的火船撞击点）。$T=0$ 时刻，这些位置就在燃烧。
• C：代表曹操的主帅指挥舰。它本质上也是一艘战船，可以被引燃。

火势每秒钟向上下左右四个方向蔓延一格（仅限战船之间）。 作为孙刘联军的军师诸葛亮，你需要计算：曹操的主帅指挥舰（C）最早在第几秒会被引燃？

如果火势无论如何都烧不到指挥舰（比如被江水隔绝），请输出 Safe。

输入格式

第一行包含两个正整数 $N, M$，表示网格的行数和列数。

接下来 $N$ 行，每行包含 $M$ 个字符，描述连环船阵的布局。字符集为 {., #, F, C}。 保证图中至少有一个 F 和一个 C。

输出格式

输出一行。 如果指挥舰会被引燃，输出一个整数，表示最早被引燃的时间（秒）。 如果指挥舰安全，输出 Safe。

输入输出样例 #1

输入：

3 4
F#..
##..
.C..

输出：

3

样例 #1 解释： 坐标 $(行, 列)$ 从 $(0,0)$ 开始。

• $T=0$: (0,0) 处是 F，开始燃烧。
• $T=1$: 火势向四周蔓延，(0,1) 和 (1,0) 处的战船被引燃。
• $T=2$: (1,0) 的火势蔓延到 (1,1) 和 (2,0)。
• $T=3$: (2,0) 的火势蔓延到 (2,1)，这正是指挥舰 C 的位置。 最短时间为 3 秒。

输入输出样例 #2

输入：

3 3
F..
.#.
..C

输出：

Safe

样例 #2 解释： 起火点 F 和指挥舰 C 之间被江水 . 完全隔开，火势无法通过对角线蔓延，因此指挥舰是安全的。

数据范围

对于 $100\%$ 的数据：

• $1 \le N, M \le 1000$
• 字符仅包含 . # F C
• 注意：可能有多个起火点 F。