Başlar üçün mükafat#10259
Vitali qumar oyunlarını oynamağı sevir. Onun sevimli oyununda nəfər iştirak edir. Oyunçular -dən -ə qədər nömrələnib. Hər bir oyunçunun iki balansı var: birincisi onun qazancı, ikincisi isə başı üçün mükafatdır. Əvvəlcə hər bir oyunçunun qazancı , başı üçün mükafat isə -dir.
Oyunda tam olaraq n-1 ardıcıl hadisə baş verir: oyundan hələ çıxmamış iki fərqli oyunçu götürülür və birincisi ikincini məğlub edir. Bu əməliyyatın nəticəsində birincinin qazancına ikincinin başı üçün mükafat əlavə edilir, birincinin başı üçün mükafata isə ikincinin başı üçün mükafatın yarısı əlavə edilir. İkinci oyunçu oyundan çıxır, yəni o artıq heç kimi məğlub edə və ya kimsə tərəfindən məğlub edilə bilməz.
Sizdən tələb olunur ki, bütün oyunçuların ümumi qazancının minimal (və ya maksimal) mümkün olması üçün hadisələrin ardıcıllığını tapın.
Birinci sətir iki tam ədəd və (2 \le n \le 10^5, 0 \le t \le 1) ehtiva edir — oyunçuların sayı və minimal və ya maksimal qazanc üçün məsələnin həll edildiyini göstərən ədəd. ədədi minimal qazanc məsələsinə, isə maksimal qazanc məsələsinə uyğundur.
n-1 sətir çıxarın. -ci sətirdə iki tam ədəd a_i və b_i (1 \leq a_i, b_i \leq n) olmalıdır, bu o deməkdir ki, -ci addımda a_i nömrəli oyunçu b_i nömrəli oyunçunu məğlub edib.
Nümunə 1
Nümunə 2
Birinci nümunəni nəzərdən keçirək. Hər addımda oyunçuların balansları:
Başlanğıc balansları: (0, 1), (0, 1), (0, 1).
Birinci addımdan sonra balanslar: (0, 1), (1, 1.5), (0, 1).
İkinci addımdan sonra balanslar: (0, 1), (2, 2), (0, 1).
Oyunçuların ümumi qazancı: 2+0+0=2
İkinci nümunəni nəzərdən keçirək. Hər addımda oyunçuların balansları:
Başlanğıc balansları: (0, 1), (0, 1), (0, 1).
Birinci addımdan sonra balanslar: (0, 1), (0, 1), (1, 1.5).
İkinci addımdan sonra balanslar: (0, 1), (1.5, 1.75), (1, 1.5).
Oyunçuların ümumi qazancı: 1+0+1.5=2.5
Testlərin -də t=0.
Digər testlərdə t=1.