Лисица Сиель хочет сделать задачку программистам на контест. Задача звучит так: «Дан простой неориентированный граф, состоящий из n вершин. Каждое его ребро имеет длину 1. Надо посчитать количество кратчайших путей между вершиной 1 и вершиной 2».
Как и все авторы, она хочет, чтобы некоторые из выходных данных были особенными: например, ее день рождения или количество ее друзей. Можете ли вы помочь ей составить такой тест для задачи, чтобы ответ на него был ровно k?
Выходные данные
Выведите граф G с n вершинами (2 ≤ n ≤ 1000). Между вершинами графа 1 и 2 должно быть ровно k наикратчайших путей.
В первой строке должно быть записано целое число n. Затем надо вывести матрицу смежности графа G, состоящую из n строк и n столбцов. Каждый элемент матрицы должен равняться 'N' или 'Y'. Если Gij равняется 'Y', то граф G имеет ребро, соединяющее вершину i и вершину j. Считайте, что вершины графа пронумерованы от 1 до n.
Граф должен быть неориентированным и простым: должны выполняться условия Gii = 'N' и Gij = Gji. Также, должен быть хотя бы один путь между вершинами 1 и 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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
4
NNYY
NNYY
YYNN
YYNN
|
|
2
|
9
|
8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN
|
|
3
|
1
|
2
NY
YN
|