Time Limit: 1s
Memory Limit: 128MB
WithCS 농장 아저씨는 농장을 둘러보던 중에 다수의 웜홀을 발견했습니다.
발견한 웜홀은 매우 놀라운 것인데요, 시간을 거슬러 단방향으로 이동하게 됩니다. 잘 활용하면 오늘 출발해서 어제 도착할 수 있는 것이죠.
각각의 농장은 N(1~500)개의 논으로 구성되고 1부터 N까지 순서 번호가 부여됩니다. 그리고 M(1~2500)개의 길이 있으며, W(1~200)개의 웜홀이 있습니다.
WithCS 아저씨는 시간 여행자에 대한 로망을 가지고 있었기에 다음과 같은 계획을 세웠습니다. 어떤 논에서 출발해서 과거의 시점에서 다시 출발지로 돌아오는 경로를 짜는 것입니다. 잘 한다면 자기 자신과 만날 수 있겠죠?
WithCS 아저씨의 로망을 이루어주기 위해 F (1~5)개의 농장을 검사해서 아저씨의 계획이 가능한지 조사해봅시다. 단, 어떠한 길도 10,000초의 시간이 소요되지 않으며, 어떠한 웜홀도 10,000초의 시간을 얻을 수 있지 않습니다.
* Line 1 : 단일 정수 F (농장의 수)
각각의 농장에 대해
* Line 1 : 3개의 정수 N, M, W
- N : 논의 수
- M : 길의 수
- W : 웜홀의 수
* Line 2 ~ M + 1 : 3개의 정수, S, E, T
- S : (양방향) 길의 시작 지점
- E : (양방향) 길의 종료 지점
- T : 길을 이용한 이동으로 소요되는 시간
* Line M+2 ~ M+W+1 : 3개의 정수, S, E, T
- S : (단방향) 웜홀의 시작 지점
- E : (단방향) 웜홀의 종료 지점
- T : 웜홀을 이용한 이동으로 얻는 시간
* Line 1 ~ F : 각각의 농장에 대해 WithCS 아저씨의 목표 달성 여부를 문자열로 표시
- 성공 시 : "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
첫번째 농장의 경우, WithCS 아저씨는 시간을 거슬러 올라갈 수 없습니다.
두번째 농장의 경우, 1-길->2-길->3-웜홀->1 을 이용하여 이동하게 되면 1초의 시간을 거슬러 올라갈 수 있습니다! 오! 이런 신기한일이.. 이 과정을 계속 반복하면 모든 밭을 시간을 얻으면서 감시할 수 있습니다.
(추가) 길의 경우 양방향으로 이동 가능하며, 웜홀의 경우 단방향으로만 이동 가능합니다.