from itertools import repeat
from array import array
import random 
import re
import sys

base_colors = (1, 2, 4) #immutable list
a, b, c = base_colors
all = a | b | c
ab = a | b	# 3
ac = a | c	# 5
bc = b | c	# 6

colors = array('B') # one byte integers; fast + mutable
edges = [ [] ] # init edges(0) to prevent off-by-one error
decisions = []
choices = { ab: (a,b), ac: (a,c), bc: (b,c) } # when the need to make a random decision strikes...

def init():
	#lines = file.readlines()
	lines = [ '1,2', '1,3', '1,4', '1,5', '2,3', '2,6', '3,6', '4,5', '4,7', '5,7', '6,7' ] # '3,6', '4,7' or '3,7', '4,6'
	extractor = re.compile("(\d+),(\d+)")
	for line in lines:
		match = extractor.match(line)
		x = int(match.group(1))
		y = int(match.group(2))
		if x not in edges:
			edges.append( [] )
		edges[x].append( y ) # assumes input is ordered ascendingly by x; will fail otherwise
	return lines[-1][-1] # largest value

largest = init()
largest = int(largest) # not sure why this is necessary; lines[-1][-1] is an int in init(), but seems to get converted to str as it comes out

if largest < 4:
	print 'Graph too small; of course it\'s colorable!'
	sys.exit()


# if largest is 7, then colors ranges from 0 to 7, and stores what color each numbered vertex can possibly be
# -- one bit on means one color; no bits means it can't be colored; multiple bits means it could go either way
colors.extend( repeat(all, largest) ) # init colors array with all -- logical, as at the beginning, any node can be any color
colors[0:2] = array('B', range(3)) # The First Two Are Free -- nodes 1 and 2 need no computation

#print 'colors: %s' % colors

# now the real fun begins

def search(start):
	impeding_color = colors[start]
	
	for i in range(start, largest):
#		print '...\n'
#		print i
#		print edges[i]
#		print 'impeding color: %u; opposite: %u' % (impeding_color, all & ~impeding_color)
		
		for j in edges[i]: # edge connecting nodes i and j
			oldcolor = colors[j]
			newcolor = oldcolor & ~impeding_color # the inverse of the impeding color gives us the possible colors; the new color is the logical AND of existing and possible
									#3 lines equiv to (if colors[j] &= ~impeding_color) but clearer
			if newcolor == 0: # means none of the colors would work here
				if len(decisions) > 0:	# maybe one of the random decisions we made is causing a lockup
					choice = decisions.pop()
					i = choice[0] # choice[1] is "nextcolor", that is, the two colors that we chose from
					colors[i] = choice[1] & ~colors[i] # invert the randomly-chosen color
#					print 'reneged on %u; changed to %s' % (i, colors[i])
					return i # equivalent to calling search(i), but saves us from recursive storage penalties
				else:
					return -j # negative signals a stop; no decisions to change means no solution
			else:
				colors[j] = newcolor
#				print 'colors[%u] = %u' % (j, newcolor)
		# end for
		next = i+1
		impeding_color = colors[next] # make sure that the next color we'll be using is a single color
		#print 'impeding color is now: %s' % impeding_color
		
		if impeding_color not in base_colors:
#			print ''
			choice = random.choice( choices[impeding_color] ) #multiple colors to choose from; pick one
			decisions.append( (next, impeding_color) )
			colors[next] = choice
#			print 'colors[%u] randomly = %u' % (next, choice)
#			print 'decisions: %s' % decisions
	#end for
	return -1

result = 1
while result > 0:
	result = search(result) # avoid recursion
	
	
if result == -1: # found coloring
	print '\n\n\nGraph is three-colorable all right.\n\n'
#	print "array(     [   1, 2, 3, 4, 5, 6, 7])"
	print colors
#	print "array(     [   1, 2, 4, 2, 4, 1, 2])"
else: # unresolvable conflict
	print '\n\n\nVertex %u is conflicted' % abs(result)
#	print "array(     [   1, 2, 3, 4, 5, 6, 7])"
	print colors
#	print "array(     [   1, 2, 4, 2, 4, 1, 2])"
#	print decisions