시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB0000.000%

문제

Bitimaa koosneb $N$ linnast, mis on nummerdatud $1, \ldots, N$. Linnad on omavahel ühendatud $M$ 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}$, 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 $K$ tundi.

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

입력

Sisendi esimesel real on kolm täisarvu $N$, $M$ ja $K$ ($1 \le N, M, K \le 3 \cdot 10^5$). Järgnevad $M$ rida; iga rida koosneb kahest täisarvust $A$ ja $B$ ($1 \le A, B \le N$, $A \ne B$) ja kirjeldab maanteed linnade $A$ ja $B$ vahel.

출력

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

예제 입력 1

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

예제 출력 1

1 1
9 4
1 1
2 1

Saab näidata, et kui Juku alustab linnast 3, on tal optimaalne teleportida nii kaua, kuni ta telepordib mingisse muusse linna ja seejärel liikuda mööda maanteid. Kui Juku alustab mõnest muust linnast, on tal optimaalne ainult mööda maanteid liikuda.

Vaatleme juhtu, kus Juku alustab linnast 3. Tõenäosusega $\frac{4}{5}$ jõuab ta mingisse teise linna esimese teleportimisega, tõenäosusega $\frac{1}{5} \cdot \frac{4}{5}$ teisel katsel, tõenäosusega $\frac{1}{5} \cdot \frac{1}{5} \cdot \frac{4}{5}$ kolmandal katsel jne. Keskmiselt on katsete arv \[ 1 \cdot \frac{4}{5} + 2 \cdot \frac{1}{5} \cdot \frac{4}{5} + 3 \cdot \frac{1}{5} \cdot \frac{1}{5} \cdot \frac{4}{5} + \cdots = 1,25. \] Pärast edukalt teleportimist on ta:

  • tõenäosusega $\frac14$ linnas 1, kust enam liikuda vaja ei ole;
  • tõenäosusega $\frac12$ linnas 2 või 4; kummastki on vaja läbida 1 maantee;
  • tõenäosusega $\frac14$ linnas 5, kust on vaja läbida 2 maanteed.

Kokku kulub tal keskmiselt seega \[ 1,25 + \frac14 \cdot 0 + \frac12 \cdot 1 + \frac14 \cdot 2 = 2,25 = \frac{9}{4} \] tundi.

예제 입력 2

6 9 100
3 4
3 2
6 5
3 6
6 1
6 4
5 4
5 1
2 1

예제 출력 2

1 1
2 1
2 1
1 1
1 1

Selles näites on teleportimine väga kallis, seega on Jukul mõistlik alati minna mööda maanteid.

예제 입력 3

15 17 3
14 7
13 6
14 10
1 7
2 12
4 12
4 5
6 10
15 2
13 4
12 15
8 2
9 11
13 10
5 2
2 11
3 9

예제 출력 3

7 1
318 39
5 1
78 13
2892 723
1 1
8 1
4982 611
3 1
8 1
6 1
5348 1337
2 1
14 2

Juhime tähelepanu, et väljundis olevad murrud ei pea olema taandatud. Näiteks viimasel real on murd $\frac{14}{2}$, mis on sama, mis $\frac{7}{1}$.