There are people numbered through . Person wants to become close to person .
You may create a friendship between any two distinct people. Friendships are undirected, and a pair of people may have at most one friendship. Define the closeness distance as the minimum number of friendship edges needed to travel from person to person . If , then .
Create exactly friendships so that all people are connected. Minimize
Print the minimum value and a set of friendships attaining it. It is allowed that .
The input is given from Standard Input in the following format:
Print the minimum total closeness distance on the first line.
On each of the next lines, print two space-separated person indices to make friends. Each edge must satisfy and . Do not print the same unordered pair twice. All people must be connected.
The total distance in the printed relationships must equal the minimum printed on the first line. If several answers exist, print any of them. The edges may be printed in any order, and the two endpoints of each edge may appear in either order.
| 4 | 38 | No additional constraints. |