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;

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; }
template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
 
#define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
#define ALL(v) (v).begin(), (v).end()
#define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}
#define fr first
#define sc second
 
typedef pair< int , int > Pi;
typedef pair< int , Pi > Pii;
 
typedef long long int64;
const int INF = 1 << 30;

struct edge{
  int to, cost;
};
struct edge2{
  int u, v, cost;
  bool operator<(const edge2& hoge)const{
    return cost < hoge.cost;
  }
};
typedef vector< vector< edge > > Graph;
typedef vector< edge2 > Edges; /* 辺集合 */

void add_edge(Graph& info, int u, int v, int cost, bool flag = true){
  info[u].push_back( (edge){ v, cost});
  if(flag) info[v].push_back( (edge){ u, cost});
}
int Dijkstra(Graph& info, int s, int g, Graph& graph) { //sからgへの最短路
  typedef pair< int, int > Pi;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  vector< int > min_cost;
  min_cost.resize(info.size(), -1);
  que.push( Pi( 0, s));
  min_cost[s] = 0;
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    if(p.second == g) return p.first;
    if(p.first > min_cost[p.second]) continue;
    for(int i = 0; i < info[p.second].size(); i++){
      edge& e = info[p.second][i];
      if(min_cost[e.to] == -1 || p.first + e.cost < min_cost[e.to]){
        min_cost[e.to] = p.first + e.cost;
        que.push( Pi( min_cost[e.to], e.to));
        graph[e.to].clear(); /* 最短ルートではない */
      }
      if(p.first + e.cost == min_cost[e.to]){
        add_edge( graph, e.to, p.second, -1, false); /* 最短ルート */
      }
    }
  }
  return -1;
}

Graph Make_Dag(Graph& graph, int start){
  vector< bool > used(graph.size(), false);
  queue< int > Que;
  Graph ret(graph.size());

  Que.push(start);
  used[start] = true;
  while(!Que.empty()){
    int idx = Que.front(); Que.pop();
    for(int i = 0; i < graph[idx].size(); i++){
      edge& e = graph[idx][i];
      add_edge( ret, e.to, idx, -1, false);
      if(used[e.to]) continue;
      used[e.to] = true;
      Que.push(e.to);
    }
  }
  return ret;
}

void dfs(int idx, vector< bool >& used, Graph& graph, vector< int >& ret){
  used[idx] = true;
  for(int i = 0; i < graph[idx].size(); i++){
    edge& e = graph[idx][i];
    if(!used[e.to]) dfs( e.to, used, graph, ret);
  }
  ret.push_back(idx);
}

vector< int > Topological(Graph& graph){
  vector< int > ret;
  vector< bool > used(graph.size(), false);
  for(int i = 0; i < graph.size(); i++){
    if(!used[i]) dfs( i, used, graph, ret);
  }
  reverse( ret.begin(), ret.end());
  return ret;
}


void solve(Graph& graph, vector< int >& edges, vector< Pi >& query){
  vector< unsigned long long int > dp(graph.size());
  for(int _ = 0; _ < query.size(); _ += 64){
    int start = _, end = min< int >( _ + 64, query.size());
    fill( dp.begin(), dp.end(), 0uLL);
    for(int i = start; i < end; i++){
      dp[query[i].first] |= 1uLL << (i - start);
    }
    for(int __ = 0; __ < edges.size(); __++){
      int j = edges[__];
      if(dp[j] == 0uLL) continue;
      for(int k = 0; k < graph[j].size(); k++){
        dp[graph[j][k].to] |= dp[j];
      }
    }
    for(int i = start; i < end; i++){
      puts( ((dp[query[i].second] >> (i - start)) & 1) ? "Yes" : "No");
    }
  }
}

int main(){
  int S, R;
  scanf("%d %d", &S, &R);
  Graph info(S);
  for(int i = 0; i < R; i++){
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    u--, v--;
    add_edge( info, u, v, w);
  }
  int a, b, Q;
  scanf("%d %d %d", &a, &b, &Q);
  a--, b--;

  Graph graph(S);
  Dijkstra( info, a, -1, graph);
  Graph ret = Make_Dag(graph, b);
  vector< int > rets = Topological(ret);
  vector< Pi > query(Q);
  for(int i = 0; i < query.size(); i++){
    scanf("%d %d", &query[i].first, &query[i].second);
    query[i].first--, query[i].second--;
  }
  solve( ret, rets, query);
  return(0);
}