Kaktusun intiqamı

NE(E)RC əvvəlki illərdə kaktuslarla - hər bir kənarı ən çox bir sadə dövrəyə aid olan əlaqəli istiqamətsiz qraflarla bağlı bir sıra məsələlər təqdim etmişdir. İntuisiya ilə kaktus, bəzi dövrələrin icazə verildiyi ağacın ümumiləşdirilməsidir. Ənənəvi kaktus, ilk dəfə NEERC 2005 məsələsində istifadə edilmişdir və "Nümunələr" bölməsindəki ikinci şəkildə göstərilmişdir.

Sizə n tam ədədi d[1], d[2], ..., d[n] verilir. n zirvəli bir kaktus qurun ki, zirvə i dərəcəsi d[i] olsun (yəni dəqiq d[i] insident kənarları), ya da belə bir kaktusun mövcud olmadığını müəyyən edin. Çoxlu kənarlar və döngələr icazə verilmir.

Giriş məlumatları

Birinci sətirdə bir tam ədəd n (2 ≤ n ≤ 2000) - kaktusdakı zirvələrin sayı verilir. İkinci sətirdə n tam ədədi d[1], d[2], ..., d[n] (1 ≤ d[i] ≤ n - 1) - zirvələrin istənilən dərəcələri verilir.

Çıxış məlumatları

Əgər şərtlərə uyğun kaktus qurmaq mümkün deyilsə, -1 çıxarın.

Əks halda, ənənəyə uyğun olaraq qurulmuş kaktusu kənarları üst-üstə düşməyən yollar dəsti kimi çıxarın.

Birinci sətirdə m tam ədədini - belə yolların sayını çıxarın. Növbəti m sətirin hər biri qrafda bir yolu əhatə etməlidir. Yol bir tam ədəd k[i] (k[i] ≥ 2) ilə başlamalıdır, ardınca 1-dən n-ə qədər olan k[i] tam ədədləri gəlməlidir. Bu k[i] ədədləri bir yolun ardıcıl zirvələrini təmsil etməlidir. Yolun qonşu zirvələri fərqli olmalıdır. Yol eyni zirvəni bir neçə dəfə ziyarət edə bilər, lakin kaktusun hər bir kənarı bütün çıxışda dəqiq bir dəfə keçilməlidir.