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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>
   
using namespace std;
   
 
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define rforeach(it, c) for (__typeof__((c).rbegin()) it=(c).rbegin(); it != (c).rend(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CL(arr, val) memset(arr, val, sizeof(arr))
#define COPY(dest, src) memcpy(dest, src, sizeof(dest))
#define ten(n) ((long long)(1e##n))
#define bin(n) (1ull << (n))
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define revrep(i, n) for (int i = (n); i >= 0; --i)
#define pb push_back

template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }

template <class T> T round_up(T a, T b) { return (a + b - 1) / b; }

template <class T> void uniq(vector<T>& c) { sort(c.begin(), c.end()); c.erase(unique(c.begin(), c.end()), c.end()); }
 
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
  
template <class T, class U> ostream& operator<<(ostream& os, pair<T, U>& p) { os << "( " << p.first << ", " << p.second << " )"; return os; }
  
template <class T> void print(T a, int n, const string& deli = " ", int br = 1) { for (int i = 0; i < n; ++i) { cout << a[i]; if (i + 1 != n) cout << deli; } while (br--) cout << endl; }
template <class T> void print(const T& c, const string& deli = " ", int br = 1) { foreach (it, c) { cout << *it; if (++it != c.end()) cout << deli;--it; } while (br--) cout << endl; }
template <class T> void print2d(T a, int w, int h, int width = -1, int br = 1) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) {    if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
   
template <class T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
template <class T> void input(T* a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }

void fix_pre(int n) { cout.setf(ios::fixed, ios::floatfield); cout.precision(10); }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
#define trace(x) (cout << #x << ": " << (x) << endl)
 
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }


typedef long long ll;
typedef pair<int, int> pint;
 
// y(v): v>^<  y(^): ^>v<
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

const double PI = acos(-1.0);

#define F first
#define S second


bool topo_dfs(int v, const vector<vector<int> >& g, vector<int>& color, vector<int>& order)
{
    color[v] = 1;
    for (int i = 0; i < (int)g[v].size(); ++i)
    {
        int to = g[v][i];
        if (color[to] == 2)
            continue;
        else if (color[to] == 1)
            return false;
        else if (!topo_dfs(to, g, color, order))
            return false;
    }
    color[v] = 2;

    order.push_back(v);
    return true;
}
// O(V + E)
// impossible -> return empty vector
vector<int> topological_sort(const vector<vector<int> >& g)
{
    const int n = g.size();

    vector<int> color(n);
    vector<int> order;

    for (int i = 0; i < n; ++i)
        if (color[i] == 0 && !topo_dfs(i, g, color, order))
            return vector<int>();
    reverse(all(order));
    return order;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    static vector<pint> g[ten(5)];
    rep(i, m)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        --u, --v;
        g[u].pb(pint(v, w));
        g[v].pb(pint(u, w));
    }

    int a, b, Q;
    scanf("%d%d%d", &a, &b, &Q);
    --a, --b;

    // 最短経路グラフを作るためにdijkstraします
    static vector<int> prev[ten(5)];
    int dis[ten(5)];
    {
        const int inf = ten(9);
        priority_queue<pint, vector<pint>, greater<pint> > q;

        fill_n(dis, n, inf);
        dis[a] = 0;
        q.push(pint(0, a));
        while (!q.empty())
        {
            int cost = q.top().first;
            int v = q.top().second;
            q.pop();

            if (cost > dis[v])
                continue;

            rep(i, g[v].size())
            {
                int to = g[v][i].first;
                int ncost = cost + g[v][i].second;
                if (ncost < dis[to])
                {
                    dis[to] = ncost;
                    q.push(pint(ncost, to));

                    prev[to].clear();
                }

                if (ncost == dis[to])
                    prev[to].pb(v);
            }
        }
    }


    // 最短経路グラフを作ります
    vector<vector<int> > min_g(n);
    {
        queue<int> q;
        static bool visit[ten(5)];
        fill_n(visit, n, false);

        visit[b] = true;
        q.push(b);
        while (!q.empty())
        {
            int v = q.front();
            q.pop();

            rep(i, prev[v].size())
            {
                int pre = prev[v][i];

                min_g[pre].pb(v);

                if (!visit[pre])
                {
                    visit[pre] = true;
                    q.push(pre);
                }
            }
        }
    }

    vector<int> order = topological_sort(min_g);
    assert(!order.empty());

    // O((Q / 64) * (V + E))
    while (Q > 0)
    {
        typedef unsigned long long ull;

        // 64クエリ or クエリがなくなるまで先読みします
        vector<int> c, d;
        while (c.size() < 64 && Q > 0)
        {
            --Q;
            int cc, dd;
            scanf("%d%d", &cc, &dd);
            --cc, --dd;
            c.pb(cc), d.pb(dd);
        }

        // dp[v]のi bit目が立っている時，c[i] -> vは最短経路上で到達可能
        static ull dp[ten(5)];
        fill_n(dp, n, 0);
        rep(i, c.size())
            dp[c[i]] |= bin(i);

        rep(i, order.size())
        {
            int v = order[i];
            rep(j, min_g[v].size())
                dp[min_g[v][j]] |= dp[v];
        }

        rep(i, c.size())
            puts((dp[d[i]] >> i & 1) ? "Yes" : "No");
    }
}