방학 중 비상 연락을 위하여 전체 학생에게 연락할 수 있는 비상 연락망을 구성하였다.

이 연락망의 구성은 반 전체 학생들을 반장을 제외하고 k개의 조로 나누고,

반장은 1조의 학생들의 전화번호를 모두 가지고 있고,

1조의 각 학생은 2조의 학생들 중 일부의 전화번호를, …, i조의 각 학생은 (i+1)조 학생들 중 일부의 전화번호를 가지고 있다.

이 연락망을 이용하여 가장 신속한 비상 연락게획을 결정하려고 한다.

비상 연락은 반장으로부터 시작하며 연락을 받은 학생은 자기가 전화번호를 가지고 있는 학생에게 전화할 수 있다.

모든 학생은 정확히 1명으로부터만 전화를 받는다.

단, 전화는 한 통화에 1분이 걸리고, 한 사람이 여러 학생에게 전화할 경우 한 명씩 순차적으로 한다.

위 그림은 비상 연락망의 예이다. 반장은 1번으로 표시하고, 나머지 학생들은 2부터 일련번호로 표시한다.

그림에서 번호가 주어진 사각형은 해당 학생들을 나타내는 노드들이고,

학생 a가 학생 b 의 전화번호를 가지고 있으면 노드 a에서 노드 b로 화살표가 주어진다.

위 그림과 같이 비상 연락망이 구성되어 있는 경우 아래의 표는 가능한 비상 연락계획 가운데 두가지를 보여주고 있다.

연락계획 A는 4분만에 연락을 완료하고, 연락계획 b는 5분이 걸린다.

주어진 연락망을 이용하여 모든 학생들에게 연락할 수 있는 가장 신속한 비상 연락계획을 세우는 프로그램을 작성하시오.

비상 연락망 timer 1초 memory 256MB

비상 연락망 1초 256MB