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<bits/stdc++.h>
using namespace std;

struct Edge {int from, to, weight;};
struct Query {int from, to;};

vector<int> Dijkstra(const vector<vector<Edge>>& edge, const int start, const int goal) {
    typedef tuple<int, int> Node;
    const int INF = INT_MAX >> 1;

    vector<int> cost(edge.size(), INF);
    priority_queue<Node, vector<Node>, greater<Node>> q;
    q.emplace(0, start);
    while(!q.empty()) {
        int c, v;
        tie(c, v) = q.top();
        q.pop();
        if(cost[v] != INF) continue;
        cost[v] = c;
        if(v == goal) break;
        for(const auto& e: edge[v]) if(cost[e.to] == INF) q.emplace(c + e.weight, e.to);
    }
    return cost;
}

vector<vector<int>> optimize(const vector<vector<Edge>>& edge, const vector<int>& cost, const int start, const int goal) {
    vector<vector<int>> outedge(edge.size());
    vector<vector<int>> inedge(edge.size());
    for(const auto& list: edge) for(const auto& e: list) {
        if(cost[e.from] + e.weight > cost[e.to]) continue;
        outedge[e.from].push_back(e.to);
        inedge[e.to].push_back(e.from);
    }

    typedef tuple<int, int> Node;
    priority_queue<Node, vector<Node>, greater<Node>> q;
    for(int v = 0; v < edge.size(); ++v) q.emplace(outedge[v].size(), v);
    vector<bool> visited(edge.size(), false);
    while(!q.empty()) {
        int outdegree, v;
        tie(outdegree, v) = q.top();
        q.pop();
        if(outdegree) break;
        if(visited[v]) continue;
        visited[v] = true;
        if(v == start || v == goal) continue;
        for(const auto& i: inedge[v]) {
            outedge[i].erase(find(outedge[i].begin(), outedge[i].end(), v));    // → ここではフラグだけ付けておいて、後で構築しなおしたほうが早いかもしれない
            q.emplace(outedge[i].size(), i);
        }
    }
    return outedge;
}

void dfs(const vector<vector<int>>& edge, const int v, vector<bool>& visited, vector<int>& order) {
    if(visited[v]) return;
    visited[v] = true;
    for(const auto& to: edge[v]) dfs(edge, to, visited, order);
    order.push_back(v);
}

vector<int> topological_sort(const vector<vector<int>>& edge, const int start, const int goal) {
    vector<int> order;
    vector<bool>visited(edge.size(), false);
    dfs(edge, start, visited, order);
    reverse(order.begin(), order.end());
    return order;
}

int main() {
    int S, R;
    cin >> S >> R;

    vector<vector<Edge>> edge(S);
    for(int i = 0; i < R; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        edge[u].push_back({u, v, w});
        edge[v].push_back({v, u, w});
    }

    int a, b;
    cin >> a >> b;
    --a; --b;

    int Q;
    cin >> Q;
    vector<Query> query;
    for(int i = 0; i < Q; ++i) {
        int c, d;
        cin >> c >> d;
        query.push_back({--c, --d});
    }

    auto cost = Dijkstra(edge, a, b);
    auto optimized_edge = optimize(edge, cost, a, b);
    auto order = topological_sort(optimized_edge, a, b);

    const int BIT = 64;
    for(int i = 0; i < Q; i += BIT) {
        vector<bitset<BIT>> dp(S);
        for(int j = 0; j < BIT && i + j < Q; ++j) dp[query[i + j].from].set(j);
        for(const auto& from: order) for(const auto& to: optimized_edge[from]) dp[to] = dp[to] | dp[from];
        for(int j = 0; j < BIT && i + j < Q; ++j) cout << (dp[query[i + j].to].test(j) ? "Yes" : "No") << endl;
    }
}