29974번 - Ralli süvakosmoses 다국어

Vastavalt Tsiolkovski valemile kulub raketi kiirendamiseks paigalseisust kiiruseni $v$ kütust kogumassiga \[ m = m_0\left(e^{\frac{v}{u}} - 1\right), \] kus $m_0$ on raketi tühimass ja $u$ 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 = 1$, $u = 1$, $e \approx 2$ ja $e^{\frac{v}{u}} \gg 1$. Sel juhul kulub raketi kiirendamiseks kiiruseni $v$ kütust $2^{v}$ ühikut.

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

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 $Q$ etapist, igas etapis on vaja liikuda mingist kontrollpunktist $p$ mingisse kontrollpunkti $q$. Leida iga etapi läbimiseks vajalik kütusekulu. Kuna kütusekulud võivad olla väga suured, väljastada nad mooduli $10^9 + 7$ järgi.

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

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

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

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