题目描述

在一个神秘岛上，有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}$