每次测试时间限制：$4$ 秒
内存限制：$512$ 兆字节
题目描述 你被给定一个无向连通图，包含 $n$ 个节点和 $m$ 条边。第 $i$ 条边的权重 $w_i$ 尚未确定，必须是一个介于 $l_i$ 和 $r_i$ 之间的实数。

你被给定一个节点 $k$。请判断是否存在一种合法的权重赋值 $(w_1,\dots,w_m)$，使得：

• 对所有 $i$ 满足 $l_i \le w_i \le r_i$，且
• $\operatorname{dist}_w(1,n) \ne \operatorname{dist}_w(1,k) + \operatorname{dist}_w(k,n)$ $^{*}$。

$^{*}$ 给定权重赋值 $w$，$\operatorname{dist}_w(u,v)$ 定义为所有从 $u$ 到 $v$ 的路径（由边序列 $e_1,\dots,e_p$ 构成）中，边权和 $w_{e_1}+\dots+w_{e_p}$ 的最小值。

输入
每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10000$）——测试用例的数量。
每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$4 \le n \le 200000$，$n-1 \le m \le 200000$，$2 \le k \le n-1$）——节点数、边数以及节点 $k$。
接下来 $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$ 之和不超过 $200000$
• 所有测试用例的 $m$ 之和不超过 $200000$

输出
对于每个测试用例，如果存在合法的权重赋值，输出 "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)$ 是可行的，因为 $\operatorname{dist}_w(1,4)=70 \ne 71 = \operatorname{dist}_w(1,2) + \operatorname{dist}_w(2,4)$。

在第二个测试用例中，不存在合法的权重赋值。