Səkkizayaqlı

Petrik dənizdəki istirahətindən evə qayıtdı və heyvanlara olan sevgisi səbəbindən bu tətil onun üçün xüsusilə yadda qalan oldu. Onun ən sevimli heyvanı isə ahtapot idi.

Evdə Petrik dərhal ahtapotlar qurmaq istədi və bunun üçün öz konstruktor dəstindən istifadə etməyə qərar verdi. Bu dəst, diskləri birləşdirmək üçün istifadə edilə bilən elastik çubuqlar dəstindən ibarətdir. Hər bir n diskində çubuqların daxil edilə biləcəyi a[i] deliklər var. Çubuq diski öz-özünə birləşdirə bilməz və hər hansı iki diski birləşdirmək üçün yalnız bir çubuq istifadə edilə bilər.

Petrikin təsəvvüründə ahtapot belə görünür:

• Ahtapotun bədəni çubuqlarla dairəvi şəkildə birləşdirilmiş üç və ya daha çox diskdən ibarətdir.

• Ahtapotun tentakulları bir-birinə çubuqlarla birləşdirilmiş bir neçə diskdən ibarətdir; tentakullar budaqlana bilər, lakin birləşə bilməz.

• Hər bir tentakul ahtapotun bədənindəki hər hansı bir diskə bir çubuqla qoşulur.

Qeyd edək ki, ahtapotun bir neçə tentakulu ola bilər və ya heç bir tentakulu olmaya bilər. Bundan əlavə, bir neçə tentakul bədəndəki bir diskə qoşula bilər. Şəkildə bəzi ahtapotlar göstərilmişdir.

Tapşırıq

Petrikə ahtapotları yığmağa kömək edin ki, aşağıdakı şərtlər yerinə yetirilsin:

• Bütün disklər istifadə edilsin.

• Hər bir diskin hər bir dəliyi çubuqla doldurulsun.

• Yığılmış ahtapotların sayı mümkün qədər çox olsun. Qeyd edək ki, bu bənd yalnız bəzi alt tapşırıqlarda məcburidir.

Giriş məlumatları:

Birinci sətirdə giriş faylında bir ədəd n (1 ≤ n ≤ 10^5) - Petrikin konstruktorundakı disklərin sayı verilir.

İkinci sətirdə n tam ədəd a[i] (1 ≤ a[i] < n) - i-ci diskdəki deliklərin sayı yazılmışdır.

Üçüncü sətir bir tam ədəd maximize ehtiva edir, bu 0-a bərabərdir, əgər ahtapotların sayını maksimuma çatdırmaq lazım deyilsə, və 1 əks halda.

Çıxış məlumatları:

Çıxış faylının birinci sətirində «Yes» yazın, əgər ahtapotları yığmaq mümkündürsə, və «No» əks halda. Müsbət cavab halında c - ahtapotların sayını yazın. Sonra n sətir yazın. Onların i-ci sətirində iki tam ədəd num[i] (1 ≤ num[i] ≤ c), p[i] - i diskə aid olan ahtapotun nömrəsi və ahtapota daha yaxın olan qonşu diskin nömrəsi yazın. Əgər disk i bədənə aiddirsə, p[i] = -1 hesab edəcəyik.

Daha yaxşı başa düşmək üçün şərtdəki nümunələrlə tanış olun.

Qiymətləndirmə