The pipes in Binbin's house were Cracked. Fortunately, Binbin is a girl with strong hands-on skills, so she plans to fix the pipe by herself. Now that Binbin has finished repairing part of the pipeline, she wants you to see if the pipeline is connected.
Formally, to give you a n*m pipeline graph, you need to judge whether the start point and the end point are connected. A pipeline graph is a graph where the starting point is at (1,0), the ending point is at (n,m+1), and the middle path is connected by pipes. For example, the following is a pipeline graph:
There are a total of the following types of pipes in Binbin’ house:
Please help Binbin to judge whether the water can flow from the starting pipe to the ending pipe in the current state.
输入描述:
The first line contains two integers n,m(1<=n,m<=2e5, 1<=n*m<=2e5).
Then, n linefollows, each line contains m integers Tij (1<=Tij<=6)– the type of pipe at(i,j).
输出描述:
If the water canflow from the starting pipe to the end pipe, output YES, otherwiseoutput NO in a single line.