CSES - Kyselyt
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Bittimaassa on nn kaupunkia, joiden välillä on mm tietä. Tehtäväsi on vastata kyselyihin, mikä on lyhin reitti kaupungista toiseen.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua nn, mm ja qq: kaupunkien määrä, teiden määrä ja kyselyiden määrä.

Sitten syötteessä on mm riviä, jotka kuvaavat tiet. Jokaisella rivillä on kolme kokonaislukua aa, bb ja cc: kaupunkien aa ja bb välillä on tie, jonka pituus on cc. Kaikki tiet ovat kaksisuuntaisia.

Lopuksi syötteessä on qq riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: reitin tulee kulkea kaupungista aa kaupunkiin bb.

Tuloste

Tulosta jokaiseen kyselyyn, kuinka pitkä on lyhin reitti kaupunkien välillä. Jos kaupunkien välillä ei ole mitään reittiä, tulosta "QAQ".

Rajat

  • 1n5001 \le n \le 500
  • 1mn21 \le m \le n^2
  • 1q1051 \le q \le 10^5
  • 1a,bn1 \le a,b \le n
  • 1c1091 \le c \le 10^9

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