401936: GYM100589 D Desolation of Smaug

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Desolation of Smaugtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Frodo Baggins is trying to run from the fury of Smaug. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and N edges.

You will be given Q queries of form St, De, S, Vf, VS which denotes:

Frodo is currently at node St and needs to reach node De. He moves with constant velocity Vf. Smaug is currently at node S and he moves with constant velocity VS. Print "YES"(quotes for clarity), if Frodo can reach destination without being caught by Smaug no matter what path Smaug takes. Else print "NO"(quotes for clarity).

Note: If Frodo reaches at destination at same time as Smaug, print "NO".

Input

First line contains N and Q, the number of nodes and number of queries respectively. Each of the next N lines contain integers u, v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge.

Each of the next Q lines contain queries.

Output

For each query print the required answer in one line.

Constraints

  • 1N, Q105
  • 1u, v, St, De, SN
  • 1VF, VS, w1000
ExamplesInput
5 2
1 2 2
2 3 3
3 4 7
4 5 5
5 1 6
1 3 5 1 2
2 4 5 2 2
Output
YES
NO

加入题单

算法标签: