Mock CCC '18 Contest 5 J5/S3 - Directed Graph Connectivity

View as PDF

Submit solution


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

Problem type

Given a directed graph of NN vertices and MM edges, determine for each edge if it is possible to reach vertex NN from vertex 11 given that that edge is deleted from the graph.

Constraints

1 \le N \le 501 \le N \le 50

1 \le M \le N^2 - N1 \le M \le N^2 - N

1 \le s_i, t_i \le N, s_i \neq t_i1 \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, NN and MM.

Each of the next MM lines contains two space-separated integers, s_is_i and t_it_i, indicating that the iith edge goes from vertex s_is_i to t_it_i.

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

Output Specification

Output MM lines.

On the iith line, given that the iith edge is deleted, print YES if it is still possible to reach vertex NN from vertex 11. Print NO otherwise.

Sample Input

3 3
1 2
2 1
2 3

Sample Output

NO
YES
NO

Comments


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

    This comment is hidden due to too much negative feedback. Click here to view it.


    • -6
      MinecraftRoblox7380  commented on Jan. 26, 2020, 9:39 a.m.

      This comment is hidden due to too much negative feedback. Click here to view it.


      • -1
        Jinx  commented on Jan. 24, 2021, 9:48 a.m. edited

        .