Bessie lại bị mắc kẹt ở phía bên kia chuồng của Farmer John, và vì thị lực quá kém, cô cần bạn giúp tìm đường đi qua chuồng.

Chuồng được mô tả bằng một lưới gồm \(N \times N\) ô vuông (\(2 \leq N \leq 20\)); một số ô trống, còn một số ô chứa các kiện cỏ khô không thể đi qua. Bessie bắt đầu ở góc dưới bên trái (ô \((1,1)\)) và muốn đi đến góc trên bên phải (ô \((N,N)\)). Bạn có thể dẫn đường cho cô bằng một dãy chỉ dẫn, mỗi chỉ dẫn là "tiến lên", "quay trái \(90\) độ" hoặc "quay phải \(90\) độ". Bạn muốn đưa ra dãy chỉ dẫn ngắn nhất có thể dẫn cô đến đích. Nếu bạn bảo Bessie đi ra ngoài lưới (tức là đâm vào tường chuồng) hoặc đi vào một kiện cỏ khô, cô sẽ không di chuyển và sẽ chuyển sang thực hiện lệnh tiếp theo trong dãy.

Đáng tiếc, Bessie không biết ban đầu mình đang quay mặt lên trên (hướng về ô \((1,2)\)) hay sang phải (hướng về ô \((2,1)\)). Bạn cần đưa ra dãy chỉ dẫn ngắn nhất có thể dẫn cô đến đích trong cả hai trường hợp. Sau khi đến đích, cô sẽ bỏ qua mọi lệnh còn lại.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu có đúng \(N\) ký tự, biểu diễn chuồng. Ký tự đầu tiên của dòng cuối cùng là ô \((1,1)\). Ký tự cuối cùng của dòng đầu tiên là ô \((N,N)\).

Mỗi ký tự là H để biểu thị một kiện cỏ khô hoặc E để biểu thị một ô trống.

Đảm bảo rằng các ô \((1,1)\) và \((N,N)\) đều trống, đồng thời tồn tại một đường đi qua các ô trống từ ô \((1,1)\) đến ô \((N,N)\).

Dữ liệu ra

In trên một dòng độ dài của dãy chỉ dẫn ngắn nhất có thể dẫn Bessie đến đích, bất kể ban đầu cô quay mặt lên trên hay sang phải.

Ví dụ

3
EHE
EEE
EEE

9

Nguồn

USACO 2017 January Contest, Gold — Cow Navigation. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=695