URI Online Judge | 3033

Help Maria

By George Albuquerque Pinto, UEVA Brazil

Timelimit: 1

Maria is a very busy computer science student. She needs to catch up on the series and watch the movie releases before she sees the spoilers. That's why she asked you to help her with the college assignment.

Maria's task given by Professor Claudio is as follows: Professor Claudio has drawn several points (with integer coordinates) on a grid $$m \times n$$ (m rows and n columns), and wants to know if this set of points is arborally satisfied. We say that a set of points $$P \in \mathbb{Z}^2$$ is arborally satisfied if for any two points $$a,b \in P$$ or a and b are on the same row or column, or if the axis-aligned rectangle with the corners a and b has at least one point of $$P \backslash \{a,b\}$$. For example, in the image below the set of points on the left is arborally satisfied while the one on the right is not.

Given a set of points $$X$$ on a grid $$m \times n$$, where point $$(i,j)$$ is on row i and column j of the grid, we want to check if $$X$$ is arborally satisfied.

Input

The input consists of multiple instances and ends with end of file (EOF). Each instance consists of three integers $$n$$, $$m$$ ($$1 \leq n,m \leq 25$$) and $$p$$ ($$1 \leq p \leq 625$$), where $$n$$ and $$m$$ indicate the size of the grid and $$p$$ the number of points of $$X$$. Then read $$p$$ lines, each with two integers $$1 \leq x_i \leq m$$ and $$1 \leq y_i \leq n$$ indicating the coordinates of point $$p_i$$.

Output

For each test case, print "Y" if set $$X$$ is arborically satisfied, or "N" otherwise.

 Input Sample Output Sample 4 4 8 1 3 2 1 2 3 3 3 3 4 4 1 4 2 4 3 4 4 6 1 3 2 1 2 3 3 4 4 1 4 2 Y N