Mock CCC '18 Contest 5 J5/S3 - Carol's Cute Chase

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

Having successfully passed his background check, Tudor is finally on his way to Google! Little does he know that Carol is attempting to surprise him by arriving there first.

Carol is currently in Canada and needs to sneak over to Google. This will require taking several flights.

Because Carol is flying Air Canada, she is sure that she will be accepted at all intermediate airports and eventually be able to arrive at Google. However, a recent law called The Last Endeavor recently passed, which allows Wicked Agents to Realistically Terminate Every flight that goes from one airport to another. This will cause mass load externally.

Carol is prepared for this contingency - if the TLE forces the WAs to RTE a given flight, is it still possible for her to fly AC to Google?


1 \le N \le 50

1 \le M \le N^2 - N

1 \le s_i, t_i \le N, s_i \neq t_i

Input Specification

The first line of the input contains two space-separated integers, N and M.

Each of the next M lines contains two space-separated integers, s_i and t_i, indicating that there are one-way flights from airport s_i to t_i.

You may assume that any given tuple (s_i, t_i) appears at most once.

Carol starts at airport 1 and wishes to get to airport N.

Output Specification

Output M lines.

On the ith line, given that the ith flight is impossible to take but all other flights are permissible, print YES if it is still possible for Carol to get to airport N from airport 1. Print NO otherwise.

Sample Input

3 3
1 2
2 1
2 3

Sample Output



  • 0
    ScriptKitty  commented on Aug. 15, 2018, 8:47 p.m.

    Legit the hardest problem I ever solved