Problem E
Drivers
Languages
de
en
et
is
lt
sv
Task
A worldwide logistics company is called Loners since all of the drivers ride alone. It is very important to the managers of the company to be able to answer their clients quickly and accurately about whether or not the drivers are going to deliver their goods safely from city $a$ to city $b$.
The driver’s job demands responsibility and alertness. For this reason, they are required to rest at a hotel no less frequently than every $p$ amount of hours. The are hotels located at every city. Using the information you have about cities and roads that connect them, write a program that would answer to the queries of the managers.
Input
On the first line three integers separated by spaces are presented: $N$ - number of cities, $M$ - number of roads, $U$ - number of manager queries. The cities are numbered from $1$ to $N$.
On the following $M$ lines, there is information about the roads presented. On each of the lines there are three integers separated by spaces: $x$, $y$ and $t$. These integers describe that it takes $t$ time to drive from city $x$ to city $y$. The roads are always two-way and it always takes the same amount of time to ride both ways. Therefore, the the condition $x < y$ is always valid in this data. The two cities can only have one direct way between them.
On the remaining $U$ amount of lines, the queries of the managers are presented. On each of the $U$ lines, three integers are presented: $a$ - the number of the initial city, $b$ - the number of the end city, $p$ - maximum amount of time that the driver can drive without rest. The condition $a < b$ will be valid.
Output
For each query, your program has to output $\texttt{TAIP}$ (Lithuanian for yes) on a separate line in case the driver can safely deliver the goods between cities $a$ and $b$. If he cannot do that, the program has to output $\texttt{NE}$ (Lithuanian for no).
Constraints
-
$1 \leq N, M, U \leq 200\, 000$
-
$1 \leq x, y, a, b \leq N$
-
$1 \leq t, p \leq 10^9$
Subtasks
|
No. |
Points |
Additional constraints |
|
1 |
10 |
$1 \leq N, M \leq 10\, 000$ and $t$ is same for all roads. |
|
2 |
11 |
$1 \leq N, M \leq 10\, 000$ and $U \le 10\, 000$. |
|
3 |
11 |
$1 \leq N, M \leq 10\, 000$ and $t \le 50$. |
|
4 |
23 |
$1 \leq N, M \leq 10\, 000$. |
|
5 |
45 |
No additional constraints. |
Examples
Even though the road between cities 1-5 exists ($1 \rightarrow 3 \rightarrow 5$), it is needed to drive for 9 hours between cities 1-3, i.e. more than the maximum amount of 6 hours.
The road between 3-4 does not exist.
There is a direct way between cities 2-4. It is possible to travel between these cities in the time that is allowed.
| 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 |
