テストケース input_16 において、S が \(2\) 個含まれているようです。

このケースについて、一方の S（任意に選んでよい）のみを . に置き換えた入力とみなして解くことで AC が得られることを確認しました。