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

View as PDF

Submit solution

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

Problem type

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


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 the ith edge goes from vertex s_i to t_i.

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

Output Specification

Output M lines.

On the ith line, given that the ith flight is deleted, print YES if it is still possible to reach vertex N from vertex 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