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

Bittimaan rataverkko muodostuu nn asemasta ja n1n-1 rataosuudesta niiden välillä. Miltä tahansa asemalta pääsee mille tahansa asemalle. Tehtäväsi on käsitellä joukko kyselyjä, joissa tehtävänä on laskea etäisyys kahden aseman välillä.

Syöte

Syötteen alussa on kaksi kokonaislukua nn ja qq: asemien määrä ja kyselyiden määrä. Asemat on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on n1n-1 riviä, jotka kuvavat rataosuudet. Jokaisella rivillä on kolme kokonaislukua aa, bb ja cc: asemien aa ja bb välissä on rataosuus, jonka pituus on cc. Kaikki rataosuudet ovat kaksisuuntaisia.

Lopuksi syötteessä on qq riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: tehtävänä on laskea etäisyys asemien aa ja bb välillä.

Tuloste

Tulosta vastaus jokaiseen kyselyyn.

Rajat

  • 1n,q1051 \le n,q \le 10^5
  • 1a,bn1 \le a,b \le n
  • 1c1091 \le c \le 10^9

Esimerkki

Syöte:

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

Tuloste:

4
9
9