# python에서의 구현 상의 이슈로 C 언어 코드 상의 getch()는 stdin.readline()으로 대체함
from __future__ import print_function
from sys import stdin

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

maxvalue = 5 	# maxvalue는 정점의 개수
n = 6 		# n은 입력개수

b = [[0 for j in range(3)] for i in range(n+1)]
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)]

printf("정점은 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

printf("%5c----------\n"%' ')
printf("%5cedge matrix\n"%' ')
for i in range(1,n+1):
	printf("%5c(%2d,%2d)\n"%(' ',b[i][1],b[i][2]))
printf("%5c----------\n"%' ')
stdin.readline()

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%5cdegree of vertex\n\n"%' ')

for i in range(1, maxvalue+1):
	printf("%5cdeg[%d] = %d\n"%(' ',i,deg[i]))
printf("%5c----------\n"%' ');
stdin.readline()

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

c = 1
cnt = 0
for k in range(1, maxvalue+1):
	if col[order[k]] == 0:
		for i in range(1,maxvalue+1):
			if a[order[k]][i] == 0 and col[i] == 0:
				col[i] = c
				cnt += 1

		if cnt == maxvalue:
			break
		else:
			c += 1

printf("\n%5cvertex coloring\n\n"%' ')
for i in range(1, maxvalue+1):
	printf("%5ccolor(v%d)=%d\n"%(' ',i,col[i]))
printf("%5c----------\n"%' ')
for i in range(1, maxvalue):
	if col[i] > col[i+1]:
		col[i+1] = col[i]
printf("이 그래프는  %d색 가능하다.\n"%col[i]);
stdin.readline()