描述

自从山上发生那起事件后，$Jack$ 和 $Jill$ 互相厌恶，希望彼此尽可能保持距离。$Jack$ 和 $Jill$ 每天都必须去上学；$Jack$ 上男校，$Jill$ 上女校，两所学校的上课时间相同。你被他们的律师聘请来安排两人的路线和时间表，以确保他们在上学途中的任意时刻的直线距离尽可能最大化。

$Jack$ 和 $Jill$ 居住的小镇是一个由 $n × n$ 的正方形网格$（n ≤ 30）$构成的地图。从一个位置走到相邻的位置需要 $1$ 分钟。在最大化两人距离时，只需考虑他们所在位置的直线距离（即无需考虑他们在移动过程中路径上的中间点）。某些位置由于河流、建筑物等原因无法通行。$Jack$ 必须从他的家出发，连续行走直到到达学校；$Jill$ 也必须同时从她的家出发，连续行走直到到达她的学校。$Jack$ 的家和学校对 $Jill$ 来说是禁行的，反之亦然。其他对两人都禁行的位置会在输入中给出。

输入格式

输入包含多个测试用例。每个测试用例的第一行是一个整数 $n$，随后是 $n$ 行，每行包含 $n$ 个字符，表示小镇的地图。在地图中：

• $'H'$ 表示$Jack$ 的家
• $'S'$ 表示$Jack$ 的学校
• $'h'$ 表示$Jill$ 的家
• $'s'$ 表示 $Jill$ 的学校
• $'*'$ 表示禁行区域
• $'.'$ 表示可通行区域

假设地图遵循常规的制图方向：上方为北，左侧为西。最后一个测试用例后是一个单独的行，包含一个 $0$。

输出格式

对于每个测试用例，输出三行：

$1$. 第一行输出 $Jack$ 和 $Jill$在上学途中的最小直线距离（保留$2$位小数）。

$2$. 第二行输出 Jack 的路线，由一系列方向组成，表示每分钟的移动方向$（'N'、'S'、'E' 或 'W'）$。

$3$. 第三行输出$Jill$的路线，格式与 $Jack$ 的路线相同。

如果有多个可行的路线组合，输出任意一种即可。题目保证至少存在一个解。连续测试用例的输出之间用空行分隔。

示例输入

10
..........
...H......
.**...s...
.**.......
.**.......
.**.......
.**.......
.**.......
...S..h..*
..........
0

示例输出

6.71
WWWSSSSSSSEEE
NEEENNNNNWWW

来源

Waterloo local 2004.01.31