이번 문제는 유니온-파인드 알고리즘을 활용하여 쉽게 해결하였다. 주어지는 두 쌍의 섬들을 합치고 부모를 구하도록 한다. 이 과정에서 갱신되지 않는 경우가 존재하기 때문에 2중 for문을 돌며 i와 j의 find 반환 값이 다를 경우에 i와 j를 출력하고 프로그램을 종료하도록 하여 해결하였다.

Code

def find(a):
    if a != parent[a]:
        parent[a] = find(parent[a])
    return parent[a]
def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
n = int(input())
parent = [i for i in range(n+1)]
for _ in range(n-2):
    a, b = map(int, input().split())
    union(a, b)
for i in range(1, n+1):
    for j in range(1, n+1):
        if find(i) != find(j):
            print(i, j)
            quit()