[재귀함수]하노이탑

##재귀 하노이 백준
def hanoi(N, a, b, c) :
    global cnt
    cnt=0
    if N==1 : 
        print(a+' '+c)
        cnt+=1
    else :
        hanoi(N-1,a, b, c)
        hanoi(1, a, c, b)
        hanoi(N-1, b, c, a)

N=int(input())
print(cnt)
hanoi(N,'1','2','3')