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?


-----Input-----

The first line contains a single integer k (1 ≤ k ≤ 10^9).


-----Output-----

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. 


-----Examples-----
Input
2
Output
4
NNYY
NNYY
YYNN
YYNN
Input
9
Output
8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN
Input
1
Output
2
NY
YN


-----Note-----

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.

Difficulty: HARD
Tags: Bit manipulation

Graph algorithms

Constructive algorithms

Implementation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
(n, m, cnt) = (int(input()), 148, 0)
ans = [['N'] * m for i in range(m)]

def edge(i, j):
	ans[i][j] = ans[j][i] = 'Y'

def node(*adj):
	global cnt
	i = cnt
	cnt += 1
	for j in adj:
		edge(i, j)
	return i
(start, end, choice) = (node(), node(), node())
if n & 1:
	edge(choice, end)
for i in range(1, 30):
	(end, choice) = (node(node(end), node(end)), node(node(choice)))
	if n & 1 << i:
		edge(choice, end)
edge(start, choice)
print(m)
for line in ans:
	print(''.join(line))


k = str(input())
l = len(k)
paths = []
for i in range(l):
	paths.append([1] * i + [int(k[i])] + [10] * (l - i - 1))
lens = [sum(p) for p in paths]
n = sum(lens) + 2
m = [''] * n
m[0] = 'N' * 2
for i in range(len(paths)):
	m[0] += 'Y' * paths[i][0] + 'N' * (lens[i] - paths[i][0])
m[1] = 'N'
for i in range(len(paths)):
	m[1] += 'N' * (lens[i] - paths[i][-1]) + 'Y' * paths[i][-1]
ind = 2
for p in paths:
	for i in range(len(p) - 1):
		for j in range(p[i]):
			m[ind] = 'N' * (p[i] - j) + 'Y' * p[i + 1] + 'N' * n
			ind += 1
	for j in range(p[-1]):
		m[ind] = 'N' * n
		ind += 1
m2 = [''] * n
for i in range(n):
	m2[i] = ''
	for j in range(i):
		m2[i] += m2[j][i]
	m2[i] += m[i][:n - i]
print(len(m2))
for s in m2:
	print(s)


k = int(input())
edges = [['N' for i in range(1010)] for j in range(1010)]
vertices = 2

def add_edge(a, b):
	nonlocal edges
	edges[a][b] = edges[b][a] = 'Y'
for i in range(1, 29 + 1):
	vertices += 3
	add_edge(i * 3, i * 3 - 1)
	add_edge(i * 3, i * 3 + 2)
	add_edge(i * 3 + 1, i * 3 - 1)
	add_edge(i * 3 + 1, i * 3 + 2)
for bit in range(30):
	if 1 << bit & k:
		lst = 1
		for i in range((29 - bit) * 2):
			vertices += 1
			add_edge(lst, vertices)
			lst = vertices
		add_edge(lst, 3 * bit + 2)
print(vertices)
if 0:
	for i in range(1, vertices + 1):
		print(i, ':', '\n\t', end='')
		for j in range(1, vertices + 1):
			if edges[i][j] == 'Y':
				print(j, end=' ')
		print('')
else:
	print('\n'.join(map(lambda x: ''.join(x[1:vertices + 1]), edges[1:vertices + 1])))


from collections import defaultdict
k = int(input())
mask = 0
d = defaultdict(lambda : 0)
while mask <= 30:
	if k & 1 << mask:
		d[mask] = 1
		ma = mask
	mask += 1
adj = defaultdict(lambda : 'N')
currl = 1
currvu = 3
prevu = [1]
prevl = []
currvl = 4
m = 4
while currl // 2 <= ma:
	if d[currl // 2]:
		adj[currvu, currvl] = 'Y'
		adj[currvl, currvu] = 'Y'
	for j in prevu:
		adj[currvu, j] = 'Y'
		adj[j, currvu] = 'Y'
	for j in prevl:
		adj[currvl, j] = 'Y'
		adj[j, currvl] = 'Y'
	if (currl + 2) // 2 <= ma:
		prevu = [currvl + 1, currvl + 2]
		for j in prevu:
			adj[currvu, j] = 'Y'
			adj[j, currvu] = 'Y'
		prevl = [currvl + 3]
		for j in prevl:
			adj[currvl, j] = 'Y'
			adj[j, currvl] = 'Y'
		currvu = currvl + 4
		currvl = currvu + 1
		m = max(m, currvl)
	else:
		break
	currl += 2
print(m)
adj[2, currvl] = 'Y'
adj[currvl, 2] = 'Y'
for i in range(1, m + 1):
	for j in range(1, m + 1):
		print(adj[i, j], end='')
	print()


(n, m) = (337, int(input()))
p = [['N'] * n for i in range(n)]

def f(i, j):
	p[i][j] = p[j][i] = 'Y'
k = 6 + 15 * 5
for j in range(2, 6):
	f(1, j)
for i in range(6, k, 5):
	for j in range(i - 4, i):
		f(i, j)
	for j in range(i + 1, i + 5):
		f(i, j)
(q, d, s) = (4 ** 15, 0, k)
while q:
	if m >= q:
		t = m // q
		m -= t * q
		if d == 0:
			for j in range(k - t, k):
				f(0, j)
		else:
			f(0, s)
			for i in range(s, s + d):
				f(i, i + 1)
			s += d
			for j in range(k - t, k):
				f(s, j)
			s += 1
	k -= 5
	d += 2
	q //= 4
print(s)
for i in range(s):
	print(''.join(p[i][:s]))


N = int(input())
b = bin(N)[2:][::-1]
count = len(b) - 1

def print_matrix(m):
	print(len(m))
	for i in range(len(m)):
		print(''.join(m[i]))
m = [['N' for i in range(2 * len(b) + count)] for j in range(2 * len(b) + count)]
for i in range(count - 1):
	val = len(m) - count + i
	m[val][val + 1] = 'Y'
	m[val + 1][val] = 'Y'
if count > 0:
	m[len(m) - 1][1] = 'Y'
	m[1][len(m) - 1] = 'Y'
c = 0
c2 = len(m) - count
for i in range(0, len(m) - count, 2):
	if i >= len(m) - 2 - count and i != 0:
		m[i][1] = 'Y'
		m[i + 1][1] = 'Y'
		m[1][i + 1] = 'Y'
		m[1][i] = 'Y'
	elif i < len(m) - 2 - count:
		m[i][i + 2] = 'Y'
		m[i][i + 3] = 'Y'
		m[i + 2][i] = 'Y'
		m[i + 3][i] = 'Y'
		if i != 0:
			m[i + 1][i + 2] = 'Y'
			m[i + 1][i + 3] = 'Y'
			m[i + 2][i + 1] = 'Y'
			m[i + 3][i + 1] = 'Y'
	if b[c] == '1':
		if i == len(m) - count - 2:
			c2 = 1
		m[i][c2] = 'Y'
		m[c2][i] = 'Y'
		if i != 0:
			m[i + 1][c2] = 'Y'
			m[c2][i + 1] = 'Y'
	c2 += 1
	c += 1
print(len(m))
for i in range(len(m)):
	print(''.join(m[i]))