CF388B.Fox and Minimal path

Fox Ciel wants to write a task for a programming contest. The task is: "You are given a simple undirected graph with n vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2."

Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to k?

Fox Ciel 想为一场编程竞赛设计一道题目。该题目的描述是：“给定一个包含 $n$ 个顶点的简单无向图，其每条边的长度均为 $1$。你需要计算从顶点 $1$ 到顶点 $2$ 的最短路径的数量。”

与某些出题人一样，她希望构造一个示例，使其答案恰好为某个特定数值（例如她的生日，或她男友的号码）。你能帮她构造一个测试用例，使得答案恰好等于 $k$ 吗？

The first line contains a single integer k (1 ≤ k ≤ 109).

第一行包含一个整数 $k$（$1 \leq k \leq 10^9$）。

You should output a graph G with n vertexes (2 ≤ n ≤ 1000). There must be exactly k shortest paths between vertex 1 and vertex 2 of the graph.

The first line must contain an integer n. Then adjacency matrix G with n rows and n columns must follow. Each element of the matrix must be 'N' or 'Y'. If G__ij is 'Y', then graph G has a edge connecting vertex i and vertex j. Consider the graph vertexes are numbered from 1 to n.

The graph must be undirected and simple: G__ii = 'N' and G__ij = G__ji must hold. And there must be at least one path between vertex 1 and vertex 2. It's guaranteed that the answer exists. If there multiple correct answers, you can output any of them.

你需要输出一个包含 $n$ 个顶点（$2 \leq n \leq 1000$）的图 $G$，使得该图中顶点 1 与顶点 2 之间恰好存在 $k$ 条最短路径。

第一行必须为一个整数 $n$。随后需给出一个 $n$ 行 $n$ 列的邻接矩阵 $G$。矩阵中每个元素必须为 'N' 或 'Y'。若 $G_{ij}$ 为 'Y'，则图 $G$ 中存在一条连接顶点 $i$ 和顶点 $j$ 的边。注意：图的顶点编号为 $1$ 到 $n$。

该图必须是无向且简单的：即对所有 $i$，有 $G_{ii} = \text{'N'}$；且对所有 $i,j$，有 $G_{ij} = G_{ji}$。此外，顶点 1 与顶点 2 之间必须至少存在一条路径。题目保证答案存在。若存在多个正确答案，输出任意一个即可。

In first example, there are 2 shortest paths: 1-3-2 and 1-4-2.

In second example, there are 9 shortest paths: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.

在第一个例子中，存在 2 条最短路径：1-3-2 和 1-4-2。

在第二个例子中，存在 9 条最短路径：1-3-6-2、1-3-7-2、1-3-8-2、1-4-6-2、1-4-7-2、1-4-8-2、1-5-6-2、1-5-7-2、1-5-8-2。