Ağacların Permutasiyaları

Bir gün cənab Kul n zirvədən ibarət bir ağac (döngəsiz, istiqamətsiz bağlı qraf) qurdu və hər bir zirvəyə i > 1 üçün iki ədəd təyin etdi: p[i] < i - zirvə i-nin birbaşa əcdadı və w[i] - zirvə i ilə p[i] arasında olan kənarın çəkisi. Zirvə 1 kökdür, buna görə onun əcdadı yoxdur.

Siz cənab Kulun hansı ağacı qurduğunu öyrənmək istədiniz, amma cənab Kul bunu deməkdən imtina etdi, lakin sizə bir ipucu verdi:

O, aşağıdakı ədədləri bir sırada yazdı və b uzunluğu 2 * n - 2 olan bir massiv əldə etdi.

b = [p[2], w[2], p[3], w[3], ..., p[n-1], w[n-1], p[n], w[n]]

Sonra o, bu massivi təsadüfi olaraq qarışdırdı və a massivini əldə etdi, sonra onu sizə verdi. Yalnız a massivinin dəyərlərini bilmək ağacı bərpa etmək üçün kifayət deyil, buna görə siz başqa bir məsələni həll etməli oldunuz.

Bir ağacı k-uzunluqlu adlandıraq, əgər zirvə 1 və n arasında olan yolda dəqiq k kənar yerləşirsə.

Bir ağacı k-mükəmməl adlandıraq, əgər o k-uzunluqlu və zirvə 1 ilə zirvə n arasında olan yoldakı kənarların çəkilərinin cəmi cənab Kulun qura biləcəyi bütün mümkün k-uzunluqlu ağaclar arasında maksimumdursa.

Sizdən zirvə 1 və zirvə n arasında olan yoldakı kənarların çəkilərinin cəmini bütün mümkün k-mükəmməl ağaclar üçün tapmaq tələb olunur. Əgər cənab Kul müəyyən bir k-uzunluqlu ağac qura bilmirsə, -1 çıxarın.

Giriş məlumatları

Birinci sətirdə bir tam ədəd n (2 ≤ n ≤ 10^5) - ağacdakı zirvələrin sayı verilir.

İkinci sətirdə 2 * n - 2 tam ədədlər a[1], a[2], ..., a[2n-2] (1 ≤ a[i] ≤ n - 1) - a massivinin elementləri verilir.

Çıxış məlumatları

Bir sətirdə n - 1 tam ədədlər w[1], w[2], w[3], ..., w[n-1] çıxarın, burada w[k] — k-mükəmməl ağacda zirvə 1 və zirvə n arasında olan yoldakı kənarların çəkilərinin cəmidir. Əgər i-uzunluqlu ağac yoxdursa, w[i] -1 olmalıdır.

İzah

Birinci nümunədə 1-mükəmməl ağac [1, 2, 1, 2] massivinə görə müəyyən edilir (yəni p[2] = 1, w[2] = 2, p[3] = 1, w[3] = 2).

2-mükəmməl ağac [1, 2, 2, 1] massivinə görə müəyyən edilir (yəni p[2] = 1, w[2] = 2, p[3] = 2, w[3] = 1). Aşağıda müvafiq olaraq 1-mükəmməl ağac və 2-mükəmməl ağacın təsvirləri verilmişdir (zirvə 1-dən zirvə n-ə olan yol qalın xətlərlə çəkilmişdir):

İkinci nümunədə a massivinin permutasiyası ilə əldə edilə bilən k-mükəmməl ağaclar yoxdur.

Üçüncü nümunədə yalnız 4-mükəmməl ağac və 5-mükəmməl ağac əldə edilə bilər. Onlar müvafiq olaraq [1, 4, 2, 4, 3, 4, 4, 4, 4, 5] və [1, 4, 2, 4, 3, 4, 4, 4, 5, 4] massivlərinə görə müəyyən edilir. Onların təsvirləri aşağıda verilmişdir: