F. Строгий треугольник
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный связный граф из $$$n$$$ вершин и $$$m$$$ ребер. Вес $$$i$$$-го ребра $$$w_i$$$ ещё не определён и должен быть действительным числом в диапазоне от $$$l_i$$$ до $$$r_i$$$.

Дана вершина $$$k$$$. Определите, существует ли допустимое присвоение весов $$$(w_1, \ldots, w_m)$$$ такое, что:

  • $$$l_i \leq w_i \leq r_i$$$ для всех $$$i$$$, и
  • $$$\mathrm{dist}_w(1, n) \neq \mathrm{dist}_w(1, k) + \mathrm{dist}_w(k, n)$$$$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$При заданных весах $$$w$$$, $$$\mathrm{dist}_w(u, v)$$$ — это минимальное значение $$$w_{e_1} + w_{e_2} + \ldots + w_{e_p}$$$ по всем последовательностям из $$$p$$$ рёбер $$$(e_1, e_2, \ldots, e_p)$$$, которые образуют путь от $$$u$$$ до $$$v$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$4 \le n \le 200\,000$$$, $$$n-1 \le m \le 200\,000$$$, $$$2 \le k \le n - 1$$$) — количество вершин, количество рёбер и вершина $$$k$$$.

В $$$i$$$-й из следующих $$$m$$$ строк содержатся четыре целых числа $$$u_i$$$, $$$v_i$$$, $$$l_i$$$ и $$$r_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$, $$$1 \le l_i \le r_i \le 10^9$$$), представляющих ребро между $$$u_i$$$ и $$$v_i$$$, вес которого должен находиться в диапазоне от $$$l_i$$$ до $$$r_i$$$ включительно. Ни одно ребро не появляется во входных данных более одного раза.

Гарантируется, что:

  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$200\,000$$$
  • сумма $$$m$$$ по всем наборам входных данных не превышает $$$200\,000$$$
Выходные данные

Выведите YES, если существует допустимое присвоение весов, и NO в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
7
4 4 2
1 2 10 20
2 3 10 30
1 3 49 90
4 3 1 1000
4 4 2
1 2 10 20
2 3 10 30
1 3 50 90
4 3 1 1000
5 7 3
1 2 1 100000
1 4 10 100
2 3 1 100000
3 4 1 100000
2 5 2 100000
3 5 1 1
4 5 1 31
5 7 3
1 2 1 100000
1 4 100000 100000
2 3 1 1
3 4 1 100000
2 5 2 100000
3 5 1 1
4 5 1 31
5 5 3
1 2 1 42
2 4 1 42
4 5 1 42
1 3 1 1
3 5 1 42
5 5 3
1 2 1 42
2 4 1 42
4 5 1 42
1 3 1 1
3 5 1 1
5 5 3
1 2 1 42
2 4 1 42
4 5 1 42
1 3 1 1
3 5 2 2
Выходные данные
YES
NO
YES
YES
YES
NO
NO
Примечание

В первом наборе входных данных $$$w = (20, 30, 49, 21)$$$ является допустимым присвоением весов, так как $$$\mathrm{dist}_w(1, 4) = 70 \neq 71 = \mathrm{dist}_w(1, 2) + \mathrm{dist}_w(2, 4)$$$.

Во втором наборе входных данных нет допустимого присвоения весов.