Effective Government Spokesman

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3179
64-bit integer IO format: %I64d      Java class name: Main

Description

Nowaday, supermarket makes our life more convenient. We can buy a lot of things in supermarket.
Now in a city, the government has built two supermarkets. And the citizens want to know whether the sum of distance between their house and the supermarket is the smallest. Let’s describe the problem more precisely. We define L1 is the distance from this house to supermarket A, L2 is the distance from this house to supermarket B, and D = L1 + L2. If there is no other house which has smaller D than this house, then this house is on the shortest road between supermarket A and supermarket B. Now the government needs your help to answer the citizen's question: Whether their house is built on the shortest path between supermarket A and supermarket B.

Input

The first line of input is a single integer T, indicating the number of test cases. Following that are exactly t cases. In each case, the first line contains two integers: N, the number of houses, and M, the number of roads. Then M lines will follow, each of which contains three integers A B C, indicating there is a road between place A and B, whose length is C. Please note that all roads are undirected. The last line contains two integers A, B (A != B) separated by a space, indicating the location of the two supermarket. The next line contains an integer Q, the number of questions that citizens had asked. Then Q lines follow, each line contain a integer p, indicate the number of the house. There is only one road between any pair of places. There must exists a path between two places.

1<= T <= 50;
5 <= N <= 100;
N – 1 <= M <= (N * (N - 1)) / 2;
1<= A, B, Q, Q<= N;
1 <= C < 1000;

Output

For each test case, print Q lines, each of which you should print ”Yes” if this house is on the shortest road between supermarket A and supermarket B , or "No" otherwise.

Sample Input

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

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

Sample Output

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .