# C 언어 코드의 getch()는 파이썬에서 stdin.readline()으로 대체함
from __future__ import print_function
from sys import stdin

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

maxvalue = 5    # 정점의 수
n = 6           # 입력할 간선의 수

# 입력할 간선들을 저장하기 위한 (nx2) 이차원 배열 선언 및 초기화 
b = [[0 for j in range(3)] for i in range(n+1)]
# 입력할 간선들을 저장하기 위한 (nxn) 인접행렬 선언 및 초기화 
a = [[0 for j in range(maxvalue+1)] for i in range(maxvalue+1)]


order = [0 for i in range(maxvalue+1)]   # 차수 기준으로 정점들을 내림차순으로 저장할 배열 선언 및 초기화
deg = [0 for i in range(maxvalue+1)]  # 각 정점의 차수에 대한 배열 선언 및 초기화
col = [0 for i in range(maxvalue+1)]  # 각 정점의 색에 대한 배열 선언 및 초기화

# 5개 정점으로 구성된 그래프에 대한 간선들을 입력받고 a와 b에 대입
printf("정점이 5개인 그래프이다(정점의 라벨은 1~5이다.)\n")
printf("간선을 1 2와 같은 순서쌍으로 6개 입력하라.\n")
for i in range(1, n+1):
    values = stdin.readline().strip('\n').split()
    b[i][1] = int(values[0])
    b[i][2] = int(values[1])
    a[b[i][1]][b[i][2]] = 1
    a[b[i][2]][b[i][1]] = 1

# 각 정점에 대한 차수를 계산해서 배열 deg에 대입
for i in range(1, maxvalue+1):
    for j in range(1, maxvalue+1):
        if a[i][j] != 0:
            deg[i] = deg[i] + 1

# 계산된 차수의 값들을 출력
printf("\n\n%5c각 정점에 대한 차수가 다음과 같다.\n\n"%' ')

for i in range(1,  maxvalue+1):
    if i == maxvalue:
        printf("%5c정점 %d의 차수는 %2d이다.\n" %(' ',i,deg[i]))
    else:
        printf("%5c정점 %d의 차수는 %2d,\n" %(' ',i,deg[i]))

# order 배열을 초기화
for i in range(1, maxvalue+1):
    order[i] = i

# 정점들을 차수에 따라 내림차순으로 정렬
for i in range(1, maxvalue):
    for j in range(i+1, maxvalue+1):
        if deg[order[i]] < deg[order[j]]:
            temp = order[i]
            order[i] = order[j]
            order[j] = temp

# 각 정점을 착색하는 반복문
for i in range(1,maxvalue + 1):
    v = order[i]

    # 현재 정점에서 착색되지 않은 최소의 색을 찾음
    usedColors = [False for i in range(maxvalue+1)]
    for adjVertex in range(1, maxvalue + 1):
        if a[v][adjVertex] == 1 and col[adjVertex] != 0:
            usedColors[col[adjVertex]] = True

    # 사용하지 않는 최소의 색을 현재 정점에 대입
    for c in range(1, maxvalue + 1):
        if not (usedColors[c]):
            col[v] = c
            break

# 색의 수를 세기
col_number = -1
for i in range(1, maxvalue):
    if col[i] >= col_number:
        col_number = col[i]


# 착색된 그래프에 대한 정보를 출력
printf("\n%5c정점을 착색한 결과는 다음과 같다.\n\n"%' ')

for colors in range(1, col_number + 1):
    print("%5c정점 "%' ', end = "")
    for i in range(1, maxvalue+1):
        if col[i] == colors:
            print(i, end = ",")    
    print(end="\b(들)이")
    print(" %d번째 색으로 착색됨" %colors)

printf("\n%5c이 그래프는 %d색 가능하다.\n\n"%(' ',col_number));
