Ralli süvakosmoses

문제

Vastavalt Tsiolkovski valemile kulub raketi kiirendamiseks paigalseisust kiiruseni $vv$ kütust kogumassiga \[ m = m_0\left(e^{\frac{v}{u}} - 1\right), \] kus $m_{0}m\_0$ on raketi tühimass ja $uu$ kütuse heitekiirus. Valem töötab tingimusel, et kiirendamise käigus tehakse kütusepaak tühjaks.

Selles ülesandes eeldame, et raketi kütusepaak on lõputu mahuga, $m_0=1m\_0\; =\; 1$, $u=1u\; =\; 1$, $e\approx 2e\; \backslash approx\; 2$ ja $e^{\frac{v}{u}}\gg 1e^\{\backslash frac\{v\}\{u\}\}\; \backslash gg\; 1$. Sel juhul kulub raketi kiirendamiseks kiiruseni $vv$ kütust $2^{v}2^\{v\}$ ühikut.

Kosmoses korraldatakse ralli, mis koosneb $VV$ kontrollpunktist ja $EE$ kahesuunalisest takistusrajast, mis ühendavad kontrollpunkte. Takistusraja number $kk$ läbimiseks on vaja kiirendada rakett kiiruseni $kk$.

Iga kontrollpunkti läbimiseks peab rakett täielikult peatuma, kusjuures pidurdamine kütust ei kuluta. Kontrollpunktides on võimalik raketi kütusepaaki täita.

Lisaks on teada, et ühtki kontrollpunktide paari ei ühenda rohkem kui üks takistusrada, ükski takistusrada ei ühenda mõnda kontrollpunkti iseendaga ja igast kontrollpunktist pääseb mööda takistusradu igasse teise kontrollpunkti.

Ralli koosneb $QQ$ etapist, igas etapis on vaja liikuda mingist kontrollpunktist $pp$ mingisse kontrollpunkti $qq$. Leida iga etapi läbimiseks vajalik kütusekulu. Kuna kütusekulud võivad olla väga suured, väljastada nad mooduli ${10}^9+710^9\; +\; 7$ järgi.

입력

Tekstifaili esimesel real on kolm tühikutega eraldatud täisarvu: kontrollpunktide arv $VV$ ($1\le V\le {10}^{5}1\; \backslash le\; V\; \backslash le\; 10^5$), takistusradade arv $EE$ ($1\le E\le 3\cdot {10}^{5}1\; \backslash le\; E\; \backslash le\; 3\; \backslash cdot\; 10^5$) ning etappide arv $QQ$ ($1\le Q\le {10}^{5}1\; \backslash le\; Q\; \backslash le\; 10^5$).

Järgmisel $EE$ real on igaühel kaks tühikuga eraldatud täisarvu $aa$ ja $bb$ ($1\le a\le V1\; \backslash le\; a\; \backslash le\; V$, $1\le b\le V1\; \backslash le\; b\; \backslash le\; V$), mis näitavad, et kontrollpunktid $aa$ ja $bb$ on ühendatud kahesuunalise takistusrajaga. Faili real number $k+1k\; +\; 1$ kirjeldatakse takistusrada number $kk$.

Järgmisel $QQ$ real on igaühel kaks tühikuga eraldatud täisarvu $pp$ ja $qq$ ($1\le p\le V1\; \backslash le\; p\; \backslash le\; V$, $1\le q\le V1\; \backslash le\; q\; \backslash le\; V$), mis näitavad, mis kontrollpunktides etapp vastavalt algab ja lõppeb.

출력

Tekstifaili väljastada $QQ$ rida, igale reale ühe etapi läbimise minimaalne kütusekulu. Etappide kütusekulud väljastada samas järjekorras, milles etapid sisendis anti.

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

16
6
4