Berlandiyanın dəmir yolları
Berləndiya hökuməti ölkədə sürətli dəmir yolu sistemi qurmağa qərar verib. Berləndiyada n şəhər var və bu şəhərlər 1-dən n-ə qədər nömrələnib. Bəzi şəhər cütləri arasında sürətli dəmir yolları qurulması planlaşdırılır. Hər bir dəmir yolu, birləşdirdiyi şəhərlər arasında hər iki istiqamətdə hərəkət etməyə imkan verəcək.
Sürətli dəmir yolları gələcəyin nəqliyyat vasitəsidir, buna görə də dəmir yolları vasitəsilə hər hansı bir şəhərdən digərinə çatmaq mümkün olmalıdır. Xərcləri minimuma endirmək üçün bu şərti yerinə yetirmək üçün lazım olan minimum sayda yol tikilməlidir.
i-ci şəhərin hökuməti digər şəhərlərə dəqiq d[i] qatarı xidmət etməyə hazırdır. Buna görə də i-ci şəhərdən çıxan dəmir yollarının sayı d[i]-ə bərabər olmalıdır. Xoşbəxtlikdən, d[1] + d[2] + ... + d[n] = 2n - 2 olduğu məlumdur.
Hökumət istəyir ki, sakinlər şəhərlər arasında mümkün qədər az sayda dəyişmə ilə hərəkət edə bilsinlər. Elə bir dəmir yolu sistemi planı hazırlamaq lazımdır ki, bir şəhərdən digərinə çatmaq üçün lazım olan maksimum dəyişmə sayı mümkün qədər az olsun.
Giriş məlumatları
Birinci sətir Berləndiyadakı şəhərlərin sayı olan n tam ədədini ehtiva edir (2 ≤ n ≤ 200 000). Növbəti sətirdə n tam ədədi d[1], d[2], ..., d[n] (1 ≤ d[i] < n) verilmişdir. Hər hansı bir şəhər i üçün, onunla birləşdirilən şəhərlərin sayı d[i]-ə bərabər olmalıdır. d[1] + d[2] + ... + d[n] = 2n - 2 olduğu təmin edilir.
Çıxış məlumatları
Optimal planda dəmir yollarının təsvirini verən n - 1 sətir çıxış edilməlidir. Hər sətir iki tam ədəd s[i] və f[i] - dəmir yolu ilə birləşdirilməli olan şəhərlərin nömrələrini ehtiva etməlidir. 1 ≤ s[i], f[i] ≤ n, s[i] ≠ f[i] şərtləri yerinə yetirilməlidir.
Hər hansı bir şəhər i üçün, onunla birləşdirilən şəhərlərin sayı d[i]-ə bərabər olmalıdır. Bir şəhərdən digərinə çatmaq üçün lazım olan maksimum dəyişmə sayı mümkün qədər az olmalıdır. Əgər bir neçə mümkün optimal dəmir yolu tikinti planı varsa, onlardan hər hansı biri çıxış edilə bilər. Bütün şərtlərə cavab verən bir planın mövcud olduğu təmin edilir.
Nümunə
Birinci testdə cavab belə bir plandır:
Görmək olar ki, hər hansı bir şəhərdən digərinə dəmir yollarından istifadə edərək çatmaq mümkündür. Həmçinin hər bir şəhər lazım olan sayda şəhərlə dəmir yolu ilə birləşdirilib. Məsələn, 1-ci şəhər üç şəhərlə birləşdirilib: 2, 4 və 6 (d[1] = 3).
Bir şəhərdən digərinə çatmaq üçün lazım olan maksimum dəyişmə sayı, məsələn, 3 və 5 şəhərləri üçün 3 dəyişmə tələb olunur. Əvvəlcə 3-cü şəhərdən 2-ci şəhərə, sonra 2-ci şəhərdən 1-ci şəhərə, sonra 1-ci şəhərdən 4-cü şəhərə və nəhayət 4-cü şəhərdən 5-ci şəhərə getmək lazımdır. Dəyişmə sayını daha az etmək mümkün olan bir plan qurmaq mümkün deyil.