K-th Path
By Gabriel Duarte, UFF 
Brazil
By Gabriel Duarte, UFF Brazil
Dabriel has just learned about shortest paths in graphs and is already considered very good at it. It can always find the best route between a pair of vertices.
After spending hours playing with his graphs and finding shortest paths he thought of something interesting: Is there any other path in the graph that uses at least K different edges of the path he had found and that the difference of the values of these paths is at most D?
As Dabriel walks around without time, he asked for your help to solve this problem. It will be given a graph and a set of edges that form a shortest path, in addition an integer Q will be given that will represent how many queries it wishes to make.
The first line of the input contains three integers N, M, Q (1 ≤ N ≤ 104, 1 ≤ M ≤ min(20000, N*(N-1) / 2), 1 ≤ Q ≤ 100), representing the quantity of vertices, the number of edges and how many queries will be made, respectively. The next line contains two integers U and V (1 ≤ U, V ≤ N, U != V), which represents the exit and destination vertex of the shortest path. The next line will have a list of integers Xi (1 ≤ Xi ≤ N) representing the ith vertex of one of the smallest paths. The next M lines describe the edges of the graph with three integers, U, V and W (1 ≤ U, V ≤ N, 1 ≤ W ≤ 105), indicating that there is an edge connecting the vertex U with vertex V with the cost W. All edges are directed and there are no two edges between the same ordered pair of vertices. In the next Q lines will have the queries with two integers K, D (1 ≤ K ≤ 100, 0 ≤ D ≤ 104).
For each query print "SIM" if there is another path with at least K different edges and with a value difference of at most D, otherwise print "NAO". The quotation marks should not be printed.
| Input Sample | Output Sample |
|
4 6 3 |
SIM |