명의 사람이 있다. 사람들에게는 부터 까지 번호가 붙어 있으며, 번 사람은 번 사람과 친해지고 싶어 한다.
서로 다른 두 사람 사이에 친구 관계를 만들 수 있다. 친구 관계는 양방향이며, 같은 두 사람 사이에는 하나만 만들 수 있다. 두 사람 사이의 친밀도 는 친구 관계를 따라 번 사람에서 번 사람에게 가는 데 필요한 친구 관계 수의 최솟값이다. 이면 이다.
정확히 개의 친구 관계를 정하여 모든 사람이 친구 관계를 통해 서로 연결되도록 하려고 한다. 각 사람이 친해지고 싶은 사람과의 친밀도 합
을 최소화하여라. 그 최솟값과 이를 달성하는 친구 관계들을 출력하여라. 인 경우도 허용된다.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄에 친밀도 합의 최솟값을 출력한다.
다음 개의 줄에 친구 관계를 맺을 두 사람의 번호 를 공백으로 구분하여 출력한다. 각 관계는 , 를 만족해야 한다. 같은 두 사람의 관계를 중복해서 출력할 수 없으며, 모든 사람이 연결되어야 한다.
출력한 관계에서 계산한 친밀도 합은 첫째 줄의 최솟값과 같아야 한다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다. 관계를 출력하는 순서와 각 관계에서 두 번호의 순서는 자유롭다.
| 4 | 38 | 추가적인 제약이 없다. |