2669 - [USACO06DEC] Wormholes G

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。

John 的每个农场有 m 条小路(无向边)连接着 n 块地(从 1 \sim n 标号),并有 w 个虫洞。

现在 John 希望能够从某块地出发,走过一条路径回到出发点,且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。

输入

输入格式

输入的第一行是一个整数 T,代表测试数据的组数。

每组测试数据的格式如下:

每组数据的第一行是三个用空格隔开的整数,分别代表农田的个数 n,小路的条数 m,以及虫洞的个数 w

每组数据的第 2 到第 (m + 1) 行,每行有三个用空格隔开的整数 u, v, p,代表有一条连接 uv 的小路,经过这条路需要花费 p 的时间。

每组数据的第 (m + 2) 到第 (m + w + 1) 行,每行三个用空格隔开的整数 u, v, p,代表点 u 存在一个虫洞,经过这个虫洞会到达点 v,并回到 p 秒之前。

输出

对于每组测试数据,输出一行一个字符串,如果能回到出发时刻之前,则输出 YES,否则输出 NO

样例

输入

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

输出

NO
YES

提示

样例解释

John 只需要沿着 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 的路径一直转圈即可,每转完一圈,时间就会减少一秒。

数据范围与约定

对于 100\% 的数据,1 \le T \le 51 \le n \le 5001 \le m \le 25001 \le w \le 2001 \le p \le 10^4

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题