시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 0 0 0.000%

문제

방학 중 비상 연락을 위하여 전체 학생에게 연락할 수 있는 비상 연락망을 구성하였다. 이 연락망의 구성은 반 전체 학생들을 반장을 제외하고 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' 과 같이 출력한다.

예제 입력 1

9
1 2 3 4
2
3 5
4 6
5 7 8 9
6 8 9
7
8
9

예제 출력 1

4
1 4
1 3 4 6
1 2 3 5 6 9
5 7 6 8