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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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