{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWhile exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ\u0027s farms comprises \u003ci\u003eN\u003c/i\u003e (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 500) fields conveniently numbered 1..\u003ci\u003eN\u003c/i\u003e, \u003ci\u003eM\u003c/i\u003e (1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 2500) paths, and \u003ci\u003eW\u003c/i\u003e (1 ≤ \u003ci\u003eW\u003c/i\u003e ≤ 200) wormholes.\u003c/p\u003e\u003cp\u003eAs FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .\u003c/p\u003e\u003cp\u003eTo help FJ find out whether this is possible or not, he will supply you with complete maps to \u003ci\u003eF\u003c/i\u003e (1 ≤ \u003ci\u003eF\u003c/i\u003e ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Line 1: A single integer, \u003ci\u003eF\u003c/i\u003e. \u003ci\u003eF\u003c/i\u003e farm descriptions follow.\r\u003cbr\u003eLine 1 of each farm: Three space-separated integers respectively: \u003ci\u003eN\u003c/i\u003e, \u003ci\u003eM\u003c/i\u003e, and \u003ci\u003eW\u003c/i\u003e\r\u003cbr\u003eLines 2..\u003ci\u003eM\u003c/i\u003e+1 of each farm: Three space-separated numbers (\u003ci\u003eS\u003c/i\u003e, \u003ci\u003eE\u003c/i\u003e, \u003ci\u003eT\u003c/i\u003e) that describe, respectively: a bidirectional path between \u003ci\u003eS\u003c/i\u003e and \u003ci\u003eE\u003c/i\u003e that requires \u003ci\u003eT\u003c/i\u003e seconds to traverse. Two fields might be connected by more than one path.\r\u003cbr\u003eLines \u003ci\u003eM\u003c/i\u003e+2..\u003ci\u003eM\u003c/i\u003e+\u003ci\u003eW\u003c/i\u003e+1 of each farm: Three space-separated numbers (\u003ci\u003eS\u003c/i\u003e, \u003ci\u003eE\u003c/i\u003e, \u003ci\u003eT\u003c/i\u003e) that describe, respectively: A one way path from \u003ci\u003eS\u003c/i\u003e to \u003ci\u003eE\u003c/i\u003e that also moves the traveler back \u003ci\u003eT\u003c/i\u003e seconds."}},{"title":"Output","value":{"format":"HTML","content":"Lines 1..\u003ci\u003eF\u003c/i\u003e: For each farm, output \"YES\" if FJ can achieve his goal, otherwise output \"NO\" (do not include the quotes)."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 3 1\r\n1 2 2\r\n1 3 4\r\n2 3 1\r\n3 1 3\r\n3 2 1\r\n1 2 3\r\n2 3 4\r\n3 1 8\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNO\r\nYES\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"For farm 1, FJ cannot travel back in time.\r\u003cbr\u003eFor farm 2, FJ could travel back in time by the cycle 1-\u0026gt;2-\u0026gt;3-\u0026gt;1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this."}}]}