Задача №114831. Железные дороги Берляндии
Правительство Берляндии решило построить в стране систему скоростных железных дорог. В Берляндии \(n\) городов, пронумерованных натуральными числами от \(1\) до \(n\). Планируется соединить скоростными железными дорогами некоторые пары городов. По каждой из дорог можно будет перемещаться в обоих направлениях между городами, которые она соединит.
За скоростными железными дорогами будущее, поэтому необходимо, чтобы, используя железные дороги, из любого города можно было добраться до любого другого. В целях экономии средств было решено построить минимальное число дорог, необходимое для выполнения этого условия.
Правительство \(i\)-го города готово обслуживать ровно \(d_i\) поездов, которые будут ходить в другие города. Поэтому количество железных дорог, выходящих из \(i\)-го города, должно быть равно \(d_i\). К счастью, оказалось, что \(d_1 + d_2 + \ldots + d_n = 2n - 2\).
Правительство хочет, чтобы жители могли перемещаться между городами с как можно меньшим числом пересадок. Необходимо составить такой план системы железных дорог, чтобы максимальное число пересадок, которое необходимо сделать, чтобы добраться из одного города в другой, было как можно меньше.
Первая строка входных данных содержит целое число \(n\) — количество городов в Берляндии (\(2 \leq n \leq 200\,000\)). В следующей строке находится \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \leq d_i < n\)). Количество городов, соединённых с \(i\)-м железной дорогой, должно совпадать с \(d_i\) для любого города \(i\). Гарантируется, что \(d_1 + d_2 + \ldots + d_n = 2n - 2\).
Требуется вывести \(n-1\) строк — описание железных дорог в оптимальном плане. Каждая строка должна содержать два целых числа \(s_i\) и \(f_i\) — номера городов, которые нужно соединить железной дорогой. Должны выполняться условия \(1 \leq s_i, f_i \leq n\), \(s_i \neq f_i\).
Количество городов, соединённых с \(i\)-м городом железной дорогой, должно совпадать с \(d_i\) для любого города \(i\). Максимальное число пересадок, которое требуется, чтобы добраться из одного города в другой, должно быть как можно меньше. Если возможных оптимальных планов строительства железных дорог несколько, можно вывести любой из них. Гарантируется, что существует план, удовлетворяющий всем условиям.
В перпом примере можно заметить, что из любого города можно добраться до любого другого, используя железные дороги. Также каждый город соединен железной дорогой с нужным количеством городов. Например, город \(1\) соединен с тремя городами: \(2\), \(4\) и \(6\) (\(d_1=3\)).
Максимальное число пересадок, которое требуется сделать, чтобы доехать из одного города в другой, достигается, например, для городов \(3\) и \(5\), для этого нужно использовать \(3\) пересадки. Сначала надо доехать из города \(3\) в город \(2\), потом из города \(2\) в город \(1\), потом из города \(1\) в город \(4\) и, наконец, из города \(4\) в город \(5\). Построить план, в котором максимальное число пересадок меньше, невозможно.
7 3 2 1 2 1 2 1
1 6 1 4 1 2 6 7 4 5 2 3
4 1 2 2 1
3 2 3 4 2 1