Đường đi ngắn nhất của vua

Quân vua đứng một mình trên bàn cờ vua $8\times 8$. Nó cần di chuyển từ ô $s$ đến ô $t$ với số nước đi ít nhất.

Trong một nước đi, quân vua có thể di chuyển sang một ô có chung cạnh hoặc chung đỉnh với ô hiện tại (thông thường có $8$ ô như vậy).

Mỗi nước đi được mô tả bằng một trong $8$ ký hiệu: L (trái), R (phải), U (lên), D (xuống), và các tổ hợp hai chữ LU, LD, RU, RD cho các nước đi chéo. Ở đây "trái/phải" là giảm/tăng chữ cái cột, "lên/xuống" là tăng/giảm chữ số hàng. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Dữ liệu vào

• Dòng đầu chứa tọa độ ô $s$.
• Dòng thứ hai chứa tọa độ ô $t$.

Tọa độ mỗi ô gồm hai ký tự: ký tự đầu là chữ cái Latin thường (từ a đến h) chỉ cột, ký tự sau là chữ số (từ 1 đến 8) chỉ hàng.

Dữ liệu ra

• Dòng đầu in số nguyên $n$: số nước đi ít nhất của quân vua.
• $n$ dòng tiếp theo, mỗi dòng in một nước đi theo ký hiệu ở trên.

Ràng buộc

• $s$ và $t$ là các ô hợp lệ trên bàn cờ $8\times 8$; $s$ có thể trùng $t$ (khi đó $n=0$).

Ví dụ