7406：Percolation

SSPUer is studying a system called percolation. We model a percolation system using an n-by-n grid of sites. Each site is either open or blocked. A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites. We say the system percolates if there is a full site in the bottom row. In other words, a system percolates if we fill all open sites connected to the top row and that process fills at least one open site on the bottom row.
(For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting. )
Now, giving you the size of the system n, the number of open site m and the position (i,j) of each open site. The position of the top-left grid is (1,1) and the position of the bottom-right grid is (n,n). Your task is to calculate the sum of full sites and tell whether the system percolates or not.

For each test case, the first line contains two integers n, m, representing the size of the system and the number of open site.
There are m lines following, each contains two integer i, j, representing the position (i,j) is an open site. (1 <= i <= j <= n)

For each test case, output a single line containing an integer and a string, representing the sum of full sites and whether the system percolates, if the system percolates output “YES”, if not output “NO”.

The sample is shown on the picture below, which has 1 full site and the system does not percolate. (position (2,2) is open but not full)