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:
//Name: Railroad
//Level: 4
//Category: グラフ,Graph,最短経路,DAG
//Note:

/**
 * AからBまでの最短経路をDijkstra法で求め、そのときに使った辺のみから
 * なるDAGを構成する。
 * すると、cからdに最短経路で行けるかの判定は、このDAG上でcからdに行けるかの
 * 判定と等価になる。
 * 1クエリについて最悪全ノードの探索が必要で、これはO(N+M)になるが、
 * 到達可能かどうかは1bitしか使わないのでbit parallelで高速化ができる。
 * (N+M) × Q = 10^10 程度なので、数十倍程度の高速化をすれば制限時間に間に合う。
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <array>
#include <bitset>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef bitset<128> Flag;
const LL INF = 100000LL * 1000 * 10;

bool solve() {
    int S, R;
    if(!(cin >> S >> R)) return false;
    if(!S && !R) return false;

    array<vector<pair<int,LL>>, 100000> graph;
    array<vector<int>, 100000> dag;
    for(int i = 0; i < R; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w));
    }
    int A, B, Q;
    cin >> A >> B >> Q;
    --A; --B;

    // Find shortest path
    array<LL, 100000> memo;
    priority_queue<pair<LL,int>> q;
    LL best_cost = INF;
    fill(memo.begin(), memo.end(), INF);
    q.push(make_pair(0, A));
    memo[A] = 0;
    while(!q.empty()) {
        const LL cost = -q.top().first;
        const int cur = q.top().second;
        q.pop();
        if(cost > best_cost) break;
        if(cur == B && best_cost == INF) {
            best_cost = cost;
        }
        if(memo[cur] < cost) continue;
        for(const auto &next : graph[cur]) {
            const LL nc = cost + next.second;
            if(nc < memo[next.first]) {
                dag[next.first].clear();
                dag[next.first].push_back(cur);
                memo[next.first] = nc;
                q.push(make_pair(-nc, next.first));
            } else if(memo[next.first] == nc) {
                dag[next.first].push_back(cur);
            }
        }
    }

    array<int, 100000> ref_cnt;
    {
        array<bool, 100000> visited;
        fill(visited.begin(), visited.end(), false);
        fill(ref_cnt.begin(), ref_cnt.end(), 0);
        queue<int> q;
        q.push(B);
        visited[B] = true;
        while(!q.empty()) {
            const int cur = q.front();
            q.pop();
            for(int to : dag[cur]) {
                ref_cnt[to]++;
                if(!visited[to]) {
                    q.push(to);
                    visited[to] = true;
                }
            }
        }
    }

    // Determine reachability for each query
    array<Flag, 100000> reachable;
    array<int, 128> dest;
    for(int i = 0; i < Q; ) {
        for(auto &f : reachable) {
            f.reset();
        }
        int cnt = 0;
        for(int j = 0; j < 128 && i < Q; ++i, ++j) {
            int c, d;
            cin >> c >> d;
            --c; --d;
            reachable[d][j] = true;
            dest[j] = c;
            ++cnt;
        }
        auto rem_cnt = ref_cnt;
        queue<int> q;
        q.push(B);
        while(!q.empty()) {
            const int cur = q.front();
            q.pop();
            for(int next : dag[cur]) {
                reachable[next] |= reachable[cur];
                if(--rem_cnt[next] == 0) {
                    q.push(next);
                }
            }
        }
        for(int j = 0; j < cnt; ++j) {
            if(reachable[dest[j]][j]) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while(solve()) ;
    return 0;
}