## Mock CCO '18 Contest 4 Problem 4 - Time Travel

View as PDF

Points: 15 (partial)
Time limit: 0.3s
Memory limit: 64M

Problem type

A zergling is sent on a dangerous journey - as part of a 4-pool build, the zergling has to run to the Protoss base to harass the mining probes.

On the way to the Protoss base, the zergling encounters some wormholes that teleport the zergling to a different space and time. The zergling comes up with an ingenious idea - if she can return to the Zerg main before she was born, then she could attack the Protoss base whenever she wanted to!

Can she?

Note that beforehand, the zergling can decide which vertex to build the Zerg main at.

#### Input Specification

The first line contains an integer , the number of test cases. test cases follow.

Each test case starts with three space-separated integers, , , and .

Each of the next lines contains three space-separated integers, , , and , indicating that there is a bidirectional path connecting vertices and that take seconds to traverse.

Each of the next lines contains three space-separated integers, , , and , indicating that there is a one-way wormhole connecting vertices to that takes the zergling back seconds in the past.

#### Output Specification

For each test case, output YES if it is possible for the zergling to travel back to the Zerg main before she was born. Output NO otherwise.

#### Sample 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

#### Sample Output

NO
YES