Fox và đường đi ngắn nhất

Cho một số nguyên dương $k$. Bạn cần dựng một đồ thị vô hướng đơn $G$ sao cho số đường đi ngắn nhất giữa đỉnh $1$ và đỉnh $2$ đúng bằng $k$.

Mỗi cạnh của đồ thị có độ dài $1$. Đường đi ngắn nhất giữa hai đỉnh là đường đi có số cạnh ít nhất; số đường đi ngắn nhất là số lượng các đường đi khác nhau cùng đạt độ dài nhỏ nhất đó.

Đồ thị phải thoả mãn:

• Số đỉnh $n$ với $2\le n\le 1000$.
• Đồ thị vô hướng và đơn: không có khuyên (đỉnh không nối với chính nó) và giữa hai đỉnh có nhiều nhất một cạnh.
• Có ít nhất một đường đi giữa đỉnh $1$ và đỉnh $2$.

Dữ liệu đảm bảo luôn tồn tại đáp án. Nếu có nhiều đồ thị hợp lệ, in ra bất kỳ đồ thị nào.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $k$.

Dữ liệu ra

Dòng đầu in số nguyên $n$ — số đỉnh của đồ thị.

$n$ dòng tiếp theo, mỗi dòng gồm $n$ ký tự mô tả ma trận kề $G$. Ký tự thứ $j$ của dòng thứ $i$ là 'Y' nếu có cạnh nối đỉnh $i$ và đỉnh $j$, ngược lại là 'N'. Các đỉnh được đánh số từ $1$ đến $n$.

Ma trận phải đối xứng ($G_{ij}=G_{ji}$) và đường chéo toàn 'N' ($G_{ii}$ = 'N').

Ràng buộc

• $1\le k\le {10}^9$

Ví dụ