고장난 통신탑

2050년 부산대학교 캠퍼스에는 셀 수 없이 많은 통신탑이 서 있다. 원래 서로 다른 통신탑끼리 1 대 1로 통신할 수 있었다. 그런데 비가 세차게 내리던 날, 통신탑이 싫었던 학생들이 몰래 모든 통신탑의 정수 처리 부분을 망치로 고장 냈다. 통신탑을 수리하려면 1000년이 걸리므로, 일단 고장 난 통신탑을 그대로 쓰기로 했다. 고장 난 통신탑의 특징은 다음과 같다.

• 각 통신탑에는 1부터 시작하는 자연수 식별 번호가 무한히 주어져 있다. $i$번 통신탑의 식별 번호는 $i$이다.
• $a$번 통신탑과 $b$번 통신탑이 있을 때, 두 식별 번호의 쌍 $(a, b)$가 약수 관계이면 두 통신탑은 직접 통신할 수 있다. 약수 관계란 두 수 중 큰 수를 작은 수로 나눈 나머지가 0인 관계를 말한다.
• 1번 통신탑과 식별 번호가 짝수인 통신탑이 직접 통신할 때 드는 비용은 모두 2이다. 그 밖의 모든 직접 통신 비용은 1이다.
• $a$번 통신탑과 $c$번 통신탑이 통신할 수 있고, $c$번 통신탑과 $b$번 통신탑이 통신할 수 있으면, $a$번 통신탑과 $b$번 통신탑은 $c$번 통신탑을 거쳐 통신할 수 있다. 이때 통신 비용은 각 직접 통신 비용의 합이다.

부산대학교 총장 산지니는 통신 비용을 줄이기 위해, 임의의 통신탑 $a$와 $b$ 사이의 통신 비용이 최소가 되는 통신 경로를 구하는 프로그램을 만들려고 한다. 또한 통신 로그 관리를 최적화하기 위해, 통신 비용이 최소인 경로가 여러 개라면 경로 위 통신탑 식별 번호의 합이 최소인 경로를 구하려고 한다. 산지니는 이 일이 귀찮아서 알고리즘 동아리 PULSE에 떠넘겼다. 3시간 안에 프로그램을 만들지 않으면 동아리를 해체하겠다고 협박했다. 동아리 해체를 막으려면 최대한 빨리 프로그램을 만들어야 한다. 입력 조건 안에서 들어올 수 있는 어떤 입력이든, 경로 선택 조건을 만족하는 통신 경로는 하나뿐이다.