Hide

Problem E
Autojuhid

Languages de en et is lt sv

Ülesanne

Logistikafirma Loners autojuhid sõidavad alati üksi. Firma dispetšeritele on väga oluline vastata kiiresti ja täpselt klientide küsimustele selle kohta, kas nende kaup on võimalik ohutult linnast $a$ linna $b$ toimetada.

Autojuhi töö nõuab täpsust ja tähelepanu. Sellepärast peavad autojuhid hiljemalt iga $p$ tunni järel hotellis puhkama. Hotellid on olemas kõigis linnades. Kirjutada programm, mis linnade ja neid ühendavate teede andmete põhjal vastab dispetšerite päringutele.

Sisend

Esimesel real on kolm täisarvu: linnade arv $N$, teede arv $M$, dispetšerite päringute arv $U$. Linnad on nummerdatud $1$ kuni $N$.

Järgmisel $M$ real on teede kirjeldused. Igal real on kolm täisarvu $x$, $y$ ja $t$, mis tähendavad, et linnast $x$ linna $y$ sõitmiseks kulub $t$ tundi. Kõik teed on kahesuunalised ja sõiduaeg on mõlemas suunas sama. Sisend on antud nii, et $x < y$. Mistahes kahe linna vahel on ülimalt üks tee.

Järgmisel $U$ real on dispetšerite päringud. Igal real on kolm täisarvu: lähtelinna number $a$, sihtlinna number $b$, maksimaalne tundide arv $p$, mille juht võib puhkamata sõita. Kõigis päringutes kehtib tingimus $a < b$.

Väljund

Iga päringu kohta väljastada eraldi reale sõna $\texttt{TAIP}$ (leedu keeles jah), kui kauba toimetamine linnast $a$ linna $b$ on võimalik. Kui see pole võimalik, väljastada sõna $\texttt{NE}$ (leedu keeles ei).

Sisendi piirangud

  • $1 \leq N, M, U \leq 200\, 000$

  • $1 \leq x, y, a, b \leq N$

  • $1 \leq t, p \leq 10^9$

Alamülesanded

No.

Punktid

Lisapiirangud

1

10

$1 \leq N, M \leq 10\, 000$ ja $t$ on kõigil teedel sama.

2

11

$1 \leq N, M \leq 10\, 000$ ja $U \le 10\, 000$.

3

11

$1 \leq N, M \leq 10\, 000$ ja $t \le 50$.

4

23

$1 \leq N, M \leq 10\, 000$.

5

45

Lisapiirangud puuduvad.

Näited

Kuigi linnade $1$ ja $5$ vahel on ühendus ($1 \rightarrow 3 \rightarrow 5$), tuleks linnade $1$ ja $3$ vahel sõita $9$ tundi, mis on rohkem kui maksimaalselt lubatud $6$ tundi.

Linnade $3$ ja $4$ vahel pole ühendust.

Linnade $2$ ja $4$ vahel on tee, mis on võimalik läbida lubatud sõiduajaga.

Sample Input 1 Sample Output 1
5 3 3
1 3 9
2 4 2
3 5 8
1 5 6
3 4 100
2 4 3
NE
NE
TAIP