Description

在探索许多农场时，约翰发现了一些令人惊奇的虫洞。虫洞是非常奇特的，因为它是一条单向路径，可以将人穿越到虫洞之前的某个时间！约翰想从某个地点开始，穿过一些路径和虫洞，并在他出发前的一段时间返回起点，也许他将能够见到自己。

Format

Input

第$1$行是单个整数$F$$（1≤F ≤5）$，表示农场的数量。每个农场的第 $1$行有$3$个整数$N 、M 、W$ ，表示编号为$1～N$的$N （1≤N≤500）$块田、$M （1≤M ≤2500）$条路径和$W （1≤W ≤200）$个虫洞。第$2～M+1$行，每行都包含$3$个数字$S 、E 、T$ ，表示穿过$S$ 与$E$ 之间的路径（双向）需要$T$ 秒。两块田都可能有多个路径。第$M +2～M +W +1$行，每行都包含$3$个数字$S 、E 、T$，表示对从$S$到$E$ 的单向路径，旅行者将穿越$T$ 秒。没有路径需要超过$10 000$秒的旅行时间，没有虫洞可以穿越超过$10 000$秒。

Output

对于每个农场，如果约翰可以达到目标，则输出“YES”，否则输出“NO”。

Samples

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

来源

POJ3259