문제
농부 창호는 자신의 농지에서 블랙홀을 발견했다. 블랙홀에 들어가면 다른 농지로 이동할 수 있는데,
이 경우 시간이 거꾸로 흘러갈 수 있다.
창호의 농지는 N(1<=N<=500)개의 영역으로 구성되어있다.
영역들은 1번부터 N번으로 번호가 매겨져 있으며 M(1<=M<=2,500)개의 평범한 이동경로(간선)가 존재한다.
그리고 B(1<=B<=200)개의 블랙홀이 있다.
창호는 이 블랙홀들을 이용해서 시간을 거꾸로 돌리고 싶다.
다시 말해서, 한 농지 영역에서 출발하여 다시 출발했던 영역으로 돌아왔을 때의 시간이 과거가 되게 하려 한다.
이것이 가능한지 판단하는 프로그램을 작성하라.
입력
첫째 줄에는 테스트케이스 수 F(1<=F<=5)가 입력된다.
매 입력 케이스의 첫 줄에는 N, M, B가 입력된다.
다음 M개의 줄에 걸쳐 각 줄마다 S, E, T 세 개의 정수가 입력된다.
이동경로(간선)의 두 농지영역(노드)S, E와 이동하는데 걸리는 시간 T( 0 <= T <= 10,000)가 주어진다.
평범한 이동경로는 양방향이다.
다음 B개의 줄에 걸쳐 각 줄마다 S, E, T 세 개의 정수가 주어진다.
블랙홀은 단방향이며 S에서 E로 이동하는데 T( 0 <= T <= 10,000)만큼 시간이 거꾸로 가는 것을 의미한다.
어느 두 지역사이의 이동경로는 여러 개가 주어질 수 있다.
출력
매 테스트 케이스마다 과거로의 시간 여행이 가능한지 여부를 출력한다.
예제1
입력
2
331
122
134
231
313
321
123
234
318
출력
NO
YES
출처
USACO 2006 December Gold