# C 언어 코드에서는 Press Any Key였던 것이 Python의 구현 문제로 Press Enter Key로 변경
from __future__ import print_function
from sys import stdin

def printf(str, *args):
	print(str % args, end='')

printf("\n		### How many domain : ")
domain = int(stdin.readline())
Mrs = [[0 for j in range(0, domain)] for i in range(0, domain)]

printf("\n## Input Relation R(1..n) ##\n")
printf("ex) 1 2 (to end : -1 –1)\n")

while True:
	values = stdin.readline().strip('\n').split()
	i = int(values[0])
	j = int(values[1])
	if i == -1:
		break
	else:
		Mrs[i-1][j-1] = 1

printf("\n#### Relation Mr ####\n")
for i in range(0, domain):
	for j in range(0, domain):
		printf("%d "%Mrs[i][j])
	printf("\n")

printf("\t\t\t<<Press Enter Key>>");
stdin.readline()
printf("\n")

for i in range(0, domain):
	for j in range(i+1, i+domain):
		for k in range(i+1, i+domain):
			m = j%domain
			n = k%domain
			if Mrs[i][n] == 1 and Mrs[m][i] == 1:
				Mrs[m][n] =1

	printf("#### W%d #### \n"%(i+1))
	for s in range(0, domain):
		for t in range(0, domain):
			printf("%d "%Mrs[s][t])
		printf("\n")
	printf("\n")
	for s in range(0, domain):
		for t in range(0, domain):
			if Mrs[s][t] == 1:
				printf("(%d, %d) " %(s+1,t+1))
	printf("\n")
	printf("\t\t\t<<Press Enter Key>>")
	stdin.readline()
	printf("\n\n")

stdin.readline()