from sys import stdin
from sys import stdin

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

# setout 함수가 이항관계들로 이루어진 집합을 출력
def setout(row, col, size):
    r = 0
    c = 0
    print("R = { ", end = "")

    for r in range(0, size):
        print("(%2d, %2d)," %(row[r],col[c]), end = " ")
        c += 1
    print("\b\b }")

# matrixout 함수가 정방행렬 mx를 출력
def matrixout(mx, size):
    blanks = size * 2 + 2
    
    print("\u250c", end = "")
    for i in range(0,blanks):
        print(" ", end = "")
    print("\u2510")

    for i in range(0, size):
        print("| ", end = "")
        for j in range(0, size):
            print("%d" % mx[i][j], end = " ")
        print(" |")
    
    print("\u2514", end = "")
    for i in range(0,blanks):
        print(" ", end = "")
    print("\u2518")

# small_mat 함수가 크기가 50보다 작은 관계행렬을 계산 후 단계별로 출력 진행
def small_mat(domain):
    # 관계행렬을 위한 2차원 배열 정의 및 초기화
    Mrs = [[0 for j in range(0, domain)] for i in range(0, domain)]
    i = 0
    print("집합 A에 대한 관계들을 (멈추기 위해 -1 –1)을 입력하라.: ")
    # -1 -1이 입력될 때까지 사용자로부터 관계를 입력받으면서 Mrs에 대입 
    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[ 관계행렬 ]\n")
    matrixout(Mrs, domain)
    printf("\n")
    
    input("\t\t\t<<아무 키나 입력하라.>>")
    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))
        matrixout(Mrs, domain)      # 수정된 행렬을 출력
        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("\n\n")

# 사용자를 위해 안내문 출력
print("\n\t\t\t\u250c--------------------------\u2510")
print("\t\t\t|      와샬 알고리즘       |")
print("\t\t\t\u2514--------------------------\u2518\n\n")

# 관계행렬의 크기를 입력받음 
size = int(input("\n집합 A가 1부터 n까지의 자연수이므로 자연수 n을 입력하라.: "))

# 크기가 0이거나 0보다 작을 때 프로그램을 멈춤
if size == 0:
    exit()

if size <= 50:
    small_mat(size)
else : # 집합 A의 크기가 50보다 클 때
    org = size
    print("집합 A에 대한 관계들을 (멈추기 위해) -1 –1을 입력하라.: ")
    # 큰 행렬을 저장하기 위한 배열 2개를 선언 
    row = [] 
    col = [] 
    count = 0
    # -1 -1이 입력될 때까지 사용자로부터 관계를 입력받으면서 Mrs에 대입
    while True:
        pair = stdin.readline().strip('\n').split()
        if int(pair[0]) == -1 or int(pair[1]) == -1:
            break
        row.append(int(pair[0]))
        col.append(int(pair[1]))
        count += 1

    k = 0
    
    set_row = [None] * org   # 행렬의 특정 행을 저장하기 위한 배열
    set_col = [None] * org   # 행렬의 특정 열을 저장하기 위한 배열   

# 크기가 50보다 큰 관계행렬일 때 큰 행렬을 출력하지 않고 결과만 출력
    while k < org:
        temp_count = count
        index_row = 0
        index_col = 0

        # 해당 반복문으로 k번째 행과 열에서 1이 있는 인덱스를 저장
        for i in range(0, temp_count):
            if row[i] == k:
                set_col.append(col[i])   # k번째 행을 set_col에 저장
                index_col += 1           # k번째 행에 1 있는 셀을 세기
            
            if col[i] == k:
                set_row.append(row[i])   # k번째 열을 set_row에 저장
                index_row += 1           # k번째 열에 1 있는 셀을 세기
               
        for c in range(0, index_col):
            for r in range(0, index_row):
                i = 0
                # 집합 set_row x set_col의 관계가 원래 행렬에 존재하는지 확인
                for i in range(0, temp_count):
                    if row[i] == set_row[r] and col[i] == set_col[c]:
                        break
                # 관계 (set_row[r], set_col[c])가 행렬에 없으면 row와 col에 추가 
                if i == temp_count:
                    row.appent(set_row[r])
                    col.append(set_col[c])
                    count += 1
        k += 1 
    # 마지막 관계에 대한 출력   
    print("와샬 알고리즘을 진행한 결과에 대한 관계 R은 다음과 같다.: ")
    setout(row, col, count)
