B. Başlar üçün mükafat

Vitali qumar oyunlarını oynamağı sevir. Onun sevimli oyununda $n$ nəfər iştirak edir. Oyunçular $1$-dən $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ı $0$, başı üçün mükafat isə $1$-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.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $t$ ($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. $0$ ədədi minimal qazanc məsələsinə, $1$ isə maksimal qazanc məsələsinə uyğundur.

Çıxış verilənləri

$n-1$ sətir çıxarın. $i$-ci sətirdə iki tam ədəd $a_i$ və $b_i$ ($1\le a_i,b_i\le n$) olmalıdır, bu o deməkdir ki, $i$-ci addımda $a_i$ nömrəli oyunçu $b_i$ nömrəli oyunçunu məğlub edib.

Nümunələr

Qeyd

Birinci nümunəni nəzərdən keçirək. Hər addımda oyunçuların balansları:

1. Başlanğıc balansları: $(0,1),(0,1),(0,1)$.

2. Birinci addımdan sonra balanslar: $(0,1),(1,1.5),(0,1)$.

3. İ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ı:

1. Başlanğıc balansları: $(0,1),(0,1),(0,1)$.

2. Birinci addımdan sonra balanslar: $(0,1),(0,1),(1,1.5)$.

3. İ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$

Qiymətləndirmə

Testlərin $50\%$-də $t=0$.

Digər $50\%$ testlərdə $t=1$.