Road#6576
In a certain country, there are cities numbered from to . A civil engineer must build a public road network that connects all cities, meaning it must be possible to travel from any city to any other, possibly via intermediate cities. His team has surveyed several routes (roads between pairs of cities). Each road is bidirectional. Building a road requires certain costs: the shorter the route, the cheaper the construction.
The engineer has never planned a road network in advance. He simply chooses a road he likes and builds it until all cities are connected.
Now the engineer wants to build a road between cities and . Under pressure from the government, aiming to reduce expenses, he asks you to write a program that determines whether it is worth building this road. Your program should print "YES" if, after construction, the road will be part of the minimum road network connecting all cities. Otherwise, it should print "NO".
The first line contains the number of test cases t~(t \le 10).
Each test case begins with a line containing four integers n, m, p, and . Here n~(2 \le n \le 10000) is the number of cities, m~(1 \le m \le 20000) is the number of roads, and and q~(1 \le p, q \le n) specify the cities between which the engineer intends to build a road.
The next lines each contain three integers and w~(1 \le u, v \le n, 1 \le w \le 4 \cdot 10^5) describing an existing bidirectional road of length between cities and . All road lengths are distinct. There can be at most one road between any pair of cities. It is guaranteed that the graph is connected, i.e., there is a path between any pair of cities. All numbers are integers.
For each test case, print "YES" if the road will be part of the minimum road network. Otherwise, print "NO".
Мысал 1