Logic

Logic

Solution

Tests

One day, a classfellow from the 10^th grade came to me and proposed a logic game. He showed me this figure:

On it I numbered the segments, so I could see clearly which the segments were. I have a pencil outside the area and I have to make curves on the paper, without lifting the pencil, and by passing through all the segments only once. At the end I must be outside. My lines (curves) can intersect with each other.

I tried many times, but I couldn’t solve it.

After a long time he told me that I can’t do it. But for other shapes I noticed I can, like this one here:

I understood that sometimes it works, sometimes it doesn’t, but I want to see if you succeed in understanding why. So I’ll give you several shapes and you have to tell me if it works (YES) or not (NO).

Task

Write a program that answers YES or NO to the shapes I propose.

Input format

The input file LOGIC.IN has the following structure:

On the first line T , the number of shapes;
On the next T groups of lines there is the data for the T shapes, as follows:

On the first line of the group there is the value N representing the number of rows and columns in the matrix.

On each of the next N lines there are N numbers separated by spaces (integers between 0 and 255 included), representing the elements of the matrix.

This matrix codifies the figure in the following way:

We define a region as a continuous part of the matrix which has the same number. In other words, two neighbour cells that contain the same number stick together. Two cells are neighbours if they are on the same row and consecutive columns, or on the same column and on consecutive rows. This way, in the interior of the region there will be no segments. To these regions we add the exterior of the matrix, which is a new region. In the matrix there can be regions with the same number, but that are not connected, so they are different regions.

The segments are the line segments that separate two regions and have maximum length (that means that we can not consider two segments one after another instead of one). The shape defined by:

1 1 2

1 2 2

1 1 2

looks like in the figure below (we’ve numbered the segments) :

Between the region filled with 1 and the region filled with 2 there are 5 segments. Between the region filled with 1 and the exterior there are 3 segments, and between the region filled with 2 and the exterior there are 3 segments. To notice that the segment 10 is made out of 3 smaller segments, but we consider it as one, by definition.

Output format

The output file LOGIC.OUT has T lines, one for each test. On each line you will write YES or NO (all in CAPS) according to the test’s result.

Restrictions

0<T<11

0<N<101

Example

LOGIC.IN

1 2

3 4

1 1 2 2

3 4 4 1

LOGIC.OUT

YES

Explanation: The two figures are the first two examples.
Time limit: 1 second/test