Mr.CaXan is an ugly guy. He always has many ideas but none of them are performed. Today, during a short doze, Mr.CaXan came with a new idea. He wants to design the architecture of the compressor of air conditioner. As he knows there is a tube network behind any kind of compressor, and he can only find some scrap copper and rotten iron to realize his thought.
The tube network behind compressor is just like grids inlayed with short tubes. Some short tubes are straight and some are curved by 90 degrees.
|
|
|||||||||||||||||||||||||||||||||
| No solution | Acceptable solution |
The compressor only works if ALL of the short tubes are closed as cycles. Mr.CaXan can twist the tubes to every possible direction (0, 90, 180, 270 degrees).
Given an initial tube arrangement, you have to figure out whether Mr.CaXan can make an acceptable solution or not by twisting some tubes to other direction.
Each test case begin with 4<= N<=1000. Following N lines contain N*N grids indicating the initial network.
N=0 indicates the end of file.
For each case, print "YES" if Mr.CaXan can find an acceptable solution, otherwise, print "NO".
4 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 4 0 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0
NO YES
Migrated from old NTUJ.
pP
| No. | Testdata Range | Score |
|---|