Problem: We have decided to introduce an automatic ticket gate to the railway network of a certain country. One of the difficult issues to implement is determining whether a given ticket can move between designated stations. Each ticket has a boarding station and a getting-off station. With this ticket, you can not only "get on at the boarding station and get off at the getting off station", but you are also allowed to get on and off the train.

There are S stations on this rail network, of which Group R stations are adjacent and can be traversed in both directions without going through other stations. There is only one railroad track connecting adjacent stations. The distance between adjacent stations is the distance measured along this railroad track. There are multiple possible routes from one station to another, depending on the shape of the railway network, but the route with the shortest distance is called the shortest route. If there are multiple such routes, both are accepted as the shortest route.

You can move from station c to station d with a ticket for boarding station a and getting off station b if there is a route p that meets all of the following conditions.

* Route p is the shortest route from station a to station b.
* Route p is a route that starts from station a, goes through station c, then station d, and ends at station b. The section from station c to station d is the shortest route between these two stations.



You will be given route map and ticket information. Next, you will be given several pairs of start and end points, so write a program that determines whether you can move from the start point to the end point with that ticket.



input

The input consists of one dataset. Input data is given in the following format.


S R
u1 v1 w1
u2 v2 w2
::
uR vR wR
a b Q
c1 d1
::
cQ dQ


The numbers given on each line are separated by a single space.

The first line consists of two integers. S (2 ≤ S ≤ 100000) is the number of stations that appear on the railroad map, and R (1 ≤ R ≤ 200000) is the number of pairs of adjacent stations. The following R line is given information on the railroad tracks that directly connect adjacent stations. ui and vi (1 ≤ ui, vi ≤ S) indicate the station numbers at both ends of the i-th line. wi (1 ≤ wi ≤ 1000) is an integer representing the distance between these stations. However, numbers from 1 to S are assigned to each station without duplication, and ui ≠ vi.

The next line consists of three integers. The first two integers represent the ticket sections, where a is the boarding station and b is the getting-off station (1 ≤ a, b ≤ S). The third integer Q (1 ≤ Q ≤ 40000) indicates the number of questions. The question is given on the following Q line. ci and di (1 ≤ ci, di ≤ S) indicate the boarding and alighting stations of the i-th question. However, a ≠ b and ci ≠ di.

output

For each question, print Yes if you can move with the given ticket, or No if you can't.

Example

Input

6 7
1 2 3
1 4 1
2 3 5
4 3 1
3 6 2
4 5 2
5 6 1
1 6 6
1 6
4 3
4 6
5 6
2 6
2 5


Output

Yes
Yes
Yes
Yes
No
No

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100001

enum Type{
	from_A,
	from_B,
};

struct Edge{
	Edge(int arg_to,int arg_dist){
		to = arg_to;
		dist = arg_dist;
	}
	int to,dist;
};

struct Info{
	Info(int arg_node_id,int arg_sum_dist){
		node_id = arg_node_id;
		sum_dist = arg_sum_dist;
	}
	bool operator<(const struct Info &arg) const{ //総距離の昇順(PQ)
		return sum_dist > arg.sum_dist;
	}

	int node_id,sum_dist;
};

struct Data{
	Data(int arg_node_id,int arg_sum_dist){
		node_id = arg_node_id;
		sum_dist = arg_sum_dist;
	}
	bool operator<(const struct Data &arg) const{
		return sum_dist < arg.sum_dist;
	}
	int node_id,sum_dist;
};

int N,M;
int A,B,C,D;
int min_dist[NUM][2];
bool is_on_shortest_path[NUM],visited[NUM];
vector<Edge> G[NUM];
vector<int> DAG_G[NUM];

void dijkstra(int start,Type type){

	for(int i = 0; i < N; i++)min_dist[i][type] = BIG_NUM;
	min_dist[start][type] = 0;

	priority_queue<Info> Q;
	Q.push(Info(start,0));

	int next_node,next_dist;
	while(!Q.empty()){
		if(Q.top().sum_dist > min_dist[Q.top().node_id][type]){
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				next_node = G[Q.top().node_id][i].to;
				next_dist = Q.top().sum_dist+G[Q.top().node_id][i].dist;

				if(min_dist[next_node][type] > next_dist){
					min_dist[next_node][type] = next_dist;
					Q.push(Info(next_node,next_dist));
				}
			}
			Q.pop();
		}
	}
}

bool can_visit(int node_id,int goal){

	int next_node;

	for(int i = 0; i < DAG_G[node_id].size(); i++){
		next_node = DAG_G[node_id][i];
		if(next_node == goal)return true;

		if(min_dist[next_node][from_A] >= min_dist[D][from_A])continue; //Dより遠いノードはSKIP
		if(visited[next_node])continue;

		visited[next_node] = true; //枝分かれ後に合流する可能性あり
		if(can_visit(next_node,goal))return true;
	}
	return false;
}


int main(){

	scanf("%d %d",&N,&M);

	int from,to,dist;
	for(int loop = 0; loop < M; loop++){
		scanf("%d %d %d",&from,&to,&dist);
		from--;
		to--;
		G[from].push_back(Edge(to,dist));
		G[to].push_back(Edge(from,dist));
	}

	int num_query;
	scanf("%d %d %d",&A,&B,&num_query);
	A--;
	B--;

	//AとBからダイクストラ
	dijkstra(A,from_A);
	dijkstra(B,from_B);

	//A→B間の最短距離上に無い点を調べる
	for(int i = 0; i < N; i++){
		if(min_dist[i][from_A]+min_dist[i][from_B] == min_dist[B][from_A]){
			is_on_shortest_path[i] = true;
		}else{
			is_on_shortest_path[i] = false;
		}
	}

	vector<Data> V;
	//最短経路DAGを構成する
	for(int i = 0; i < N; i++){
		if(is_on_shortest_path[i]){
			V.push_back(Data(i,min_dist[i][from_A]));
		}
	}

	sort(V.begin(),V.end());

	int node_id,next_node;
	//最短経路DAG上のエッジを生成する
	for(int i = 0; i < V.size(); i++){
		node_id = V[i].node_id;

		for(int k = 0; k < G[node_id].size(); k++){
			next_node = G[node_id][k].to;
			if(min_dist[next_node][from_A] <= min_dist[node_id][from_A])continue; //next_nodeの方がAに近ければSKIP

			if(min_dist[node_id][from_A]+G[node_id][k].dist+min_dist[next_node][from_B] > min_dist[B][from_A])continue; //最短経路上の辺でなければSKIP

			DAG_G[node_id].push_back(next_node);
		}
	}

	for(int loop = 0; loop < num_query; loop++){
		scanf("%d %d",&C,&D);
		C--;
		D--;
		if(is_on_shortest_path[C] == false || is_on_shortest_path[D] == false ||
				min_dist[C][from_A] >= min_dist[D][from_A]){
				printf("No\n");
				continue;
		}

		for(int i = 0; i < N; i++)visited[i] = false;

		visited[C] = true;
		if(can_visit(C,D)){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}

	return 0;
}