暂无测试数据。

题目描述

原题来自：USACO 2006 Dec. Gold，原文见 POJ 3259

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John 的每个农场有 \(M\) 条小路（无向边）连接着 \(N\)（从 \(1\) 到 \(N\) 标号）块地，并有 \(W\) 个虫洞。

现在 John 想借助这些虫洞来回到过去（**在出发时刻之前回到出发点**），请你告诉他能办到吗。 John 将向你提供 \(F\) 个农场的地图。没有小路会耗费你超过 \(10^4\) 秒的时间，当然也没有虫洞回帮你回到超过 \(10^4\) 秒以前。

输入格式

第一行一个整数 \(F\)，表示农场个数；

对于每个农场：

第一行，三个整数 \(N, M, W\)；

接下来 \(M\) 行，每行三个数 \(S, E, T\)，表示在标号为 \(S\) 的地与标号为 \(E\) 的地中间有一条用时 \(T\) 秒的小路；

接下来 \(W\) 行，每行三个数 \(S, E, T\)，表示在标号为 \(S\) 的地与标号为 \(E\) 的地中间有一条可以使 John 到达 \(T\) 秒前的虫洞。

输出格式

输出共 \(F\) 行，如果 John 能在第 \(i\) 个农场实现他的目标，就在第 \(i\) 行输出 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

限制与提示

对于全部数据，\(1\le F\le 5,1\le N\le 500,1\le M\le 2500,1\le W\le 200,1\le S,E\le N,|T|\le 10^4\)。