题目背景

家里的扫地机器人小 Q 忙碌了一整天，此时电量指示灯已经开始闪烁。它必须在剩余电量耗尽（即走完 $k$ 步）之前，通过房间内错综复杂的障碍物，顺利到达任意一个充电站进行补给。如果无法在有限的电量内到达，我们需要计算它最少还需要额外增加多少步的电量才能安全“续命”。

题目描述

给定一个大小为 $n \times m$ 的方格矩阵。矩阵中包含以下字符：

扫地机器人每次可以向上、下、左、右四个方向移动一步。请问机器人能否在 $k$ 步（含 $k$ 步）之内从 s 到达最近的 t？

如果可以，输出 Yes；如果无法到达，输出 No 并输出一个整数，表示在耗尽 $k$ 步后，最少还需要多少步才能到达最近的 t。

第一行输入三个整数 $n, m, k$ （$1 \leq n \times m \leq 10^6, 0 \leq k \leq n \times m$），分别表示矩阵的行数、列数和机器人当前的剩余电量（步数）。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，由 .、#、s、t 组成。

若能在 $k$ 步内到达，输出 Yes。

若不能到达，输出 No 并在下一行输出一个整数，表示机器人到达最近的充电站还需要额外走的最少步数（如果机器人根本无法到达任何充电站，请输出 $-1$ ）。

3 4 2
s..#
.#..
#t.t

No
3

起点 s 位于 $(0,0)$ ，最近的充电站 t 分别位于 $(2,1)$ 和 $(2,3)$ 。

到达 $(2,1)$ 的最短路径长度为 $(0,0) \rightarrow (0,1) \rightarrow (0,2) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,1)$

在本样例中， $k=2$ ，因此输出 No，且还需 $3$ 步。