Fox Ciel 想要为编程竞赛编写一个任务。任务是:“给你一个有 n 个顶点的简单无向图。它的每条边都有单位长度。你应该计算顶点 1 和顶点 2 之间的最短路径的数量。”
和一些作家一样,她想用一些特定的输出来做一个例子:例如,她的生日或她男朋友的号码。你能帮她做一个答案恰好等于 k 的测试用例吗?
输入
第一行包含一个整数 k (1 ≤ k ≤ 109)。
输出
您应该输出一个具有 n 个顶点的图 G (2 ≤ n ≤ 1000)。图的顶点 1 和顶点 2 之间必须恰好有 k 条最短路径。
第一行必须包含整数 n。然后必须遵循 n 行 n 列的邻接矩阵 G。矩阵的每个元素必须是“N”或“Y”。如果 Gij 为“Y”,则图 G 具有连接顶点 i 和顶点 j 的边。考虑图的顶点从 1 到 n 编号。
图必须是无向且简单的:Gii = 'N' 且 Gij = Gji 必须成立。并且顶点1和顶点2之间必须至少有一条路径。保证答案存在。如果有多个正确答案,则可以输出其中任何一个。
示例
输入 #1
2
输出 #1
4 NNYY NNYY YYNN YYNN
输入 #2
9
输出 #2
8 NNYYYNNN NNNNNYYY YNNNNYYY YNNNNYYY YNNNNYYY NYYYYNNN NYYYYNNN NYYYYNNN
输入 #3
1
输出 #3
2 NY YN
注意
在第一个示例中,有 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。