- Time limit: 1.00 s
- Memory limit: 128 MB
Bittimaassa on kaupunkia, joiden välillä on tietä. Tehtäväsi on vastata kyselyihin, mikä on lyhin reitti kaupungista toiseen.
Syöte
Syötteen ensimmäisellä rivillä on kolme kokonaislukua , ja : kaupunkien määrä, teiden määrä ja kyselyiden määrä.
Sitten syötteessä on riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua , ja : kaupunkien ja välillä on tie, jonka pituus on . Kaikki tiet ovat kaksisuuntaisia.
Lopuksi syötteessä on riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua ja : reitin tulee kulkea kaupungista kaupunkiin .
Tuloste
Tulosta jokaiseen kyselyyn, kuinka pitkä on lyhin reitti kaupunkien välillä. Jos kaupunkien välillä ei ole mitään reittiä, tulosta "QAQ".
Rajat
Esimerkki
Syöte:
4 3 5 1 2 5 1 3 9 2 3 3 1 2 2 1 1 3 1 4 3 2
Tuloste:
5 5 8 QAQ 3