URI Online Judge | 1506

Rabito and Bones

By Bugs, Lucas y Coyote BR Brazil

Timelimit: 3

Rabito and Rayito are playing a nice game. They start with a weighted bidirectional connected graph (all weights are positive) and a set of K bones placed on some of the vertices.

They start taking turns with Rabito playing first. The game consists of moving the bones through the graph towards the vertex 1. On a turn one the players takes a subset of at least 1 and at most P of the bones (that have not reached the vertex 1) and moves these bones through one or more of the edges of the graph (the bones' moves are independent of each other) subject to this condition: he may use a particular edge for a bone if it makes that bone eventually reach the vertex 1 using the least possible amount of time (it takes A units of time to move a bone through and edge of weight A) and if the edge makes this bone eventually reach the vertex 1 using the largest amount of edges.

There's a huge bone waiting for the winner of the game, so your task is to decide which of the two dogs will triumph on this game and have a nice meal (assuming both of the dogs play with an optimal strategy). The loser of the game is, of course, the dog that cannot make a move.


The first line contains a single integer T (T <= 100) the number of test cases. The description of T test cases follows. A test case begins with a line containing two integers N, M (1 <= N <= 100, 1 <= M <= 2000) denoting the number of vertices and edges of the graph, then follow M lines each with three integers u, v, w (1 <= u, v <= N) (0 < w <= 1000000) representing the vertices of the i-th edges and its weight. Then a line with two integers K (0 < K <= 1000) and P (0 < P) denoting the number of bones initially placed on the graph and the parameter P as described in the problem statement. Finally a single line containing K integers describing the initial positions of the K bones.


Output T lines, one for each test case. If Rabito has a strategy that will guarantee his victory output "Yes", otherwise output "No".

Sample Input Sample Output

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