from copy import deepcopy

#BRUTEFORCE!!!!

Input = open("data5.txt","r").read().split("\n")

def WriteLine(Line):
    open("out5.txt","a").write(str(Line)+"\n")
    
    
def GetCombos(i,Stack):
    if i==N:
        Combos.append(Stack)
        return None
    for j in xrange(color):
        CStack = deepcopy(Stack+[j])
        GetCombos(i+1,CStack)
        
        
    

    
while Input!=[]:
    N = int(Input[0])
    del Input[:1]
    Nodes = []
    
    for i in xrange(N):
        Nodes.append([int(j)-1 for j in Input[i].split(" ")])
    del Input[:N]
    
    LenNodes = len(Nodes)
    
    Done = False
    for color in xrange(1,5):
        Combos = []
        GetCombos(0,[])
        ColorWorks = False
        #print Combos
        
        for Combo in Combos:
            Works = True
            for i in xrange(LenNodes):
                if Combo[Nodes[i][0]]==Combo[Nodes[i][1]] and Nodes[i][0]!=Nodes[i][1]:
                    Works = False
                    break
            if Works:
                ColorWorks = True
        if ColorWorks:
            WriteLine(color)
            print color
            Done = True
            break
    if not Done:
        WriteLine(0)
        print 0