| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 437 | 6 | 4 | 30.769% |
방학 중 비상 연락을 위하여 전체 학생에게 연락할 수 있는 비상 연락망을 구성하였다. 이 연락망의 구성은 반 전체 학생들을 반장을 제외하고 k개의 조로 나누고, 반장은 1조의 학생들의 전화번호를 모두 가지고 있고, 1조의 각 학생은 2조의 학생들 중 일부의 전화번호를, …, i조의 각 학생은 (i+1)조 학생들 중 일부의 전화번호를 가지고 있다. 이 연락망을 이용하여 가장 신속한 비상 연락게획을 결정하려고 한다.
비상 연락은 반장으로부터 시작하며 연락을 받은 학생은 자기가 전화번호를 가지고 있는 학생에게 전화할 수 있다. 모든 학생은 정확히 1명으로부터만 전화를 받는다. 단, 전화는 한 통화에 1분이 걸리고, 한 사람이 여러 학생에게 전화할 경우 한 명씩 순차적으로 한다.
위 그림은 비상 연락망의 예이다. 반장은 1번으로 표시하고, 나머지 학생들은 2부터 일련번호로 표시한다. 그림에서 번호가 주어진 사각형은 해당 학생들을 나타내는 노드들이고, 학생 a가 학생 b 의 전화번호를 가지고 있으면 노드 a에서 노드 b로 화살표가 주어진다.
위 그림과 같이 비상 연락망이 구성되어 있는 경우 아래의 표는 가능한 비상 연락계획 가운데 두가지를 보여주고 있다. 연락계획 A는 4분만에 연락을 완료하고, 연락계획 b는 5분이 걸린다.
| 연락계획 A | 연락계획 B | ||||
|---|---|---|---|---|---|
| 송신자 | 수신자 | 통화시각 | 송신자 | 수신자 | 통화시각 |
| 1 | 4 | 1 | 1 | 2 | 1 |
| 1 | 3 | 2 | 1 | 3 | 2 |
| 1 | 2 | 3 | 1 | 4 | 3 |
| 3 | 5 | 3 | 3 | 5 | 3 |
| 4 | 6 | 2 | 4 | 6 | 4 |
| 5 | 7 | 4 | 5 | 7 | 4 |
| 6 | 9 | 3 | 5 | 8 | 5 |
| 6 | 8 | 4 | 6 | 9 | 5 |
주어진 연락망을 이용하여 모든 학생들에게 연락할 수 있는 가장 신속한 비상 연락계획을 세우는 프로그램을 작성하시오.
첫째 줄에는 전체 반의 학생 수 n이 주어진다. 이때 n은 100이하의 정수이다. 그 다음 n개의 줄에는 각 줄마다 학생의 번호와 그 학생이 전화번호를 가지고 있는 학생들의 번호가 하나의 빈칸을 상이에 두고 주어진다.
첫째 줄에 비상 연락에 걸리는 총 시간을 분 단위로 출력하고 다음 줄부터 순서대로 매분마다 연락이 이루어지는 송신자 번호와 수신자 번호의 순서쌍들을 한 줄에 출력한다.
예를 들어, 연락계획 A에서 통화시각 2에 연락이 이루어지는 쌍은 (1,3)과 (4,6)이다. 이에 대한 출력은 아래와 같이 첫 칸에 시작하여 하나의 빈칸을 사이에 두고 '1 3 4 6' 또는 '4 6 1 3' 과 같이 출력한다.
미리 구한 정답보다 작거나 같은 답을 구해야 한다.
9 1 2 3 4 2 3 5 4 6 5 7 8 9 6 8 9 7 8 9
4 1 4 1 3 4 6 1 2 3 5 6 9 5 7 6 8