题目描述

在一个神秘岛上，有N(1 <= N <= 500)个洞口，标号1..N，它们之间有M (1 <= M <= 2500) 条通道相连。

神秘的竟然另外还有W (1 <= W <=200)条传说中的时间虫洞----当到达通道的另一端洞口时，竟然可以比进入的时间要早！

你当然想进行这样的时间之旅，希望从一个洞口s出发，经过几个通道，在比出发早些时候的时间回到洞口s。也许还能碰到自己呢,hehe 根据给定的地图，请判断能否实现这样的愿望。

给定图为连通图。

输入格式

第一行：一个整数 F (1 <= F <= 5)，表示共有F组数据。（多组数据测试）

每组数据： 第1行：三个整数 N M W

第2至M+1行:每行三个整数 (S, E, T),表示在S与E洞口之间有一个双向通道，通过需要T(0 <= T <= 10,000) 秒。

第M+2至M+W+1行:每行三个整数 (S, E, T),表示在S与E洞口之间有一个单向通道，从S到E可以回到之前T(0 <= T <= 10,000) 秒。

输出格式

共1..F行，每行对应一组数据，如果可以实现愿望输出"YES",否则输出"NO".

样例数据

input

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

output

NO
YES

数据规模与约定

usaco wormhole

时间限制：$ 1 \text {s} $

空间限制：$ 256 \text {MB} $