Kuningriigi jagamine

문제

Imperaator Informaticus III on juba üsna vana ja varsti teise ilma minemas. Tal on suur impeerium, mis koosneb $NN$ linnast ja $N-1N\; -\; 1$ maanteest. Linnad on nummerdatud $1\dots N1\; \backslash ldots\; N$. Iga maantee ühendab omavahel kaks erinevat linna ja on teada, et igast linnast on võimalik mööda neid maanteid minna igasse teise linna.

Nii suurt impeeriumi on väga raske valitseda. Tõepoolest --- kuidas muidu oleks võimalik, et riigis on ainult $N-1N\; -\; 1$ maanteed? Seetõttu otsustas imperaator riigi oma $KK$ lapse vahel ära jagada, mitte pärandada esmasündinule nagu teised imperaatorid.

Loomulikult peab see jaotus olema õiglane ja praktiline. Seega otsustati, et:

1. Iga laps peab saama sama arvu linnu.
2. Iga lapse saadav tükk peab olema sidus --- kui mingi laps saab endale linnad $uu$ ja $vv$, siis peab olema võimalik mööda maanteid liikuda linnast $uu$ linna $vv$ nii, et kõik tee peale jäävad linnad on samuti selle lapse omad.

Sina oled õukonna ülemarvutaja ja pead leidma võimaluse riik nii ära jagada või teatama, et see ei ole võimalik. Tõsi küll --- viimasel juhul võetakse sul tõenäoliselt pea maha.

입력

Faili esimesel real on linnade arv $NN$ ja laste arv $KK$ ($1\le K\le N\le 3\cdot {10}^{5}1\; \backslash le\; K\; \backslash le\; N\; \backslash le\; 3\; \backslash cdot\; 10^5$). Järgneb $N-1N\; -\; 1$ rida, kus kirjeldatakse riigi teedevõrku. Igal real on kaks arvu $uu$ ja $vv$ ($1\le u\le N1\; \backslash le\; u\; \backslash le\; N$, $1\le v\le N1\; \backslash le\; v\; \backslash le\; N$), mis näitavad et linnade $uu$ ja $vv$ vahel on maantee.

출력

Faili esimesele reale kirjutada 'SAAB', kui soovitud tükeldamine on võimalik, või 'EI SAA', kui ei ole. Kui tükeldamine on võimalik, väljastada teisele reale $NN$ tühikutega eraldatud täisarvu, kus kohal $ii$ olev arv on selle lapse number, kes saab linna $ii$. Lapsed on nummerdatud $1\dots K1\; \backslash ldots\; K$.

9 3
2 8
1 9
5 6
4 5
8 7
8 1
1 6
3 5

SAAB
1 3 2 2 2 1 3 3 1

8 4
1 2
2 3
1 4
4 5
1 6
6 7
7 8

SAAB
1 2 2 3 3 1 4 4

4 3
1 2
2 4
1 3

EI SAA

6 3
1 2
1 3
1 4
1 5
1 6

EI SAA