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~
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 ~i~th 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 ~M~ lines.
On the ~i~th line, given that the ~i~th edge is deleted,
YES if it is still possible to reach vertex ~N~ from vertex ~1~. Print
3 3 1 2 2 1 2 3
NO YES NO