给您一个无向连通图,其中包含 $$$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$$$。
以下 $$$m$$$ 行中的第 $$$i$$$ 行包含四个整数 $$$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$$$
输出
打印 是 如果存在有效的权重分配并且 NO 否则。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。
示例
输入复制
74 4 21 2 10 202 3 10 301 3 49 904 3 1 10004 4 21 2 10 202 3 10 301 3 50 904 3 1 10005 7 31 2 1 1000001 4 10 1002 3 1 1000003 4 1 1000002 5 2 1000003 5 1 14 5 1 315 7 31 2 1 1000001 4 100000 1000002 3 1 13 4 1 1000002 5 2 1000003 5 1 14 5 1 315 5 31 2 1 422 4 1 424 5 1 421 3 1 13 5 1 425 5 31 2 1 422 4 1 424 5 1 421 3 1 13 5 1 15 5 31 2 1 422 4 1 424 5 1 421 3 1 13 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)$$$。
在第二个测试用例中,没有有效的权重分配。