Rikkis teleporter

문제

Bitimaa koosneb $NN$ linnast, mis on nummerdatud $1,\dots ,N1,\; \backslash ldots,\; N$. Linnad on omavahel ühendatud $MM$ kahesuunalise maanteega: iga maantee ühendab (ilma vahepeatusteta) kaks linna. On teada, et ükski maantee ei ühenda linna iseendaga, kaks erinevat maanteed ei ühenda sama linnapaari ja et mööda maanteid on võimalik liikuda igast linnast igasse teise linna.

Juku elab linnas 1. Ühe maantee läbimiseks kulub tal 1 tund. Lisaks on Juku valduses võimas teleporter. Teleporter on aga rikkis: pärast teleporteri kasutamist satub Juku ühtlase jaotusega valitud juhuslikku linna. See tähendab, et pärast teleporteri kasutamist on iga linna korral tõenäosus $\frac{1}{N}\backslash frac\{1\}\{N\}$, et Juku satub sellesse linna. Muuhulgas võib teleporter Juku ka paigale jätta. Teleporteri ülesseadmine on keeruline ja aeganõudev tehniline töö: iga kord, kui Juku soovib teleporterit kasutada, kulub tal selleks $KK$ tundi.

Leia iga $uu$ ($2\le u\le N2\; \backslash le\; u\; \backslash le\; N$) kohta, kui kaua kulub Jukul keskmiselt linnast $uu$ linna 1 minemiseks eeldusel, et ta teeb kõik valikud optimaalselt. Saab näidata, et ülesandes kehtivate piirangute korral on otsitav keskväärtus iga $uu$ korral esituv murruna $\frac{p}{q}\backslash frac\{p\}\{q\}$, kus $pp$ ja $qq$ on täisarvud ning kehtivad $0\le p\le {10}^{18}0\; \backslash le\; p\; \backslash le\; 10^\{18\}$ ja $1\le q\le {10}^{18}1\; \backslash le\; q\; \backslash le\; 10^\{18\}$.

입력

Sisendi esimesel real on kolm täisarvu $NN$, $MM$ ja $KK$ ($1\le N,M,K\le 3\cdot {10}^{5}1\; \backslash le\; N,\; M,\; K\; \backslash le\; 3\; \backslash cdot\; 10^5$). Järgnevad $MM$ rida; iga rida koosneb kahest täisarvust $AA$ ja $BB$ ($1\le A,B\le N1\; \backslash le\; A,\; B\; \backslash le\; N$, $A\mathrm{\ne }BA\; \backslash ne\; B$) ja kirjeldab maanteed linnade $AA$ ja $BB$ vahel.

출력

Väljastada $N-1N\; -\; 1$ rida; nendest $ii$-ndale reale väljastada kaks täisarvu $pp$ ja $qq$ ($0\le p\le {10}^{18}0\; \backslash le\; p\; \backslash le\; 10^\{18\}$, $1\le q\le {10}^{18}1\; \backslash le\; q\; \backslash le\; 10^\{18\}$), mis näitavad, et linnast $i+1i\; +\; 1$ linna 1 minemiseks kulub optimaalsete valikute korral keskmiselt $\frac{p}{q}\backslash frac\{p\}\{q\}$ tundi. Murd ei pea olema taandatud.