# Prüfer Code Decoder

# Decoder 소개
print("[길이 (n-2)의 Prüfer Code를 입력받아, 원래 수형도 T를 복구하는 프로그램입니다.]\n")

while True :
    try :
        n=int(input("수형도 T의 꼭짓점 개수(n)를 입력하세요 : "))
        if n < 2 :
            print("유효하지 않은 입력입니다. n은 2 이상이어야 합니다.\n")
        else :
            break
    except ValueError :
        print("유효하지 않은 입력입니다. 정수를 입력해주세요.\n")

pCode=[]
while len(pCode)!=n-2 :
    try :
        pCode=list(map(int, input("길이 (n-2)의 Prüfer Code를 입력하세요. \n공백 없이 쉼표로 구분지어 입력합니다. (ex. 1,2,3,4,4) : \n").split(',')))
        
        if len(pCode)!=n-2 :
            print("유효하지 않은 입력입니다. 다시 입력해주세요.\n")
        elif any(c < 1 or c > n for c in pCode) :
            print(f"유효하지 않은 입력입니다. 꼭짓점 번호는 1부터 {n}까지 입력해야 합니다.\n")
            pCode=[]
            
    except ValueError :
        print("유효하지 않은 입력입니다. 정수만 입력해주세요.\n")

pCode.append(n) # 구현의 편의를 위한 append

degree=[0]*(n+1) # 각 꼭짓점의 차수-1

for c in pCode :
    degree[c]+=1
    
# 수형도 T 복구
T=[[] for _ in range(n+1)] # 수형도 T

for c in pCode : 
    leaf = next(i for i in range(1, n+1) if degree[i]==0) # 다음 연결 꼭짓점 찾기
    T[leaf].append(c)
    T[c].append(leaf)

    degree[leaf]-=1
    degree[c]-=1
    
print("입력된 Prüfer Code를 통해 복구한 수형도는 아래와 같습니다.")
print("=============================")
for i in range(1, n+1) :
    print(f"[{i}] ", end="")
    for j in T[i] :
        print(f"({i},{j})",end="")
    print()
print("=============================")