P0850

[Usaco2006 Dec]Wormholes 虫洞

[Usaco2006 Dec]Wormholes 虫洞

John 在农场中发现了许多虫洞。虫洞可以看作一条特殊的有向边，通过虫洞可以回到进入虫洞之前的某个时刻。

每个农场由 NN 块土地组成，编号为 11 到 NN。土地之间有 MM 条双向通行的小路，以及 WW 个单向通行的虫洞。经过一条小路需要花费一定时间，而经过虫洞可以回到若干秒之前。

John 想知道，他能否借助小路和虫洞回到出发时刻之前。你需要对 FF 个农场分别作出判断。

输入格式

第一行包含一个整数 FF，表示农场数量。

接下来依次输入每个农场的信息。对于每个农场：

  • 第一行包含三个整数 NN、MM、WW，分别表示土地数量、小路数量和虫洞数量；
  • 接下来 MM 行，每行包含三个整数 SS、EE、TT，表示土地 SS 与土地 EE 之间有一条双向小路，通过它需要 TT 秒；
  • 接下来 WW 行，每行包含三个整数 SS、EE、TT，表示有一个从土地 SS 指向土地 EE 的虫洞，通过它可以回到 TT 秒之前。

输出格式

对每个农场输出一行。

如果 John 能够回到出发时刻之前，输出 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≤F≤51\le F\le 5；
  • 1≤N≤5001\le N\le 500；
  • 1≤M≤25001\le M\le 2500；
  • 1≤W≤2001\le W\le 200；
  • 通过任意一条小路所需的时间不超过 10410^4 秒；
  • 任意一个虫洞使 John 回到过去的时间不超过 10410^4 秒。

来源与许可

本题为 USACO 2006 December 试题「Wormholes 虫洞」，题面与测试数据整理自 BZOJ。

样例 1

输入

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