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