ANARC07C - Rotating Rings

Any square grid can be viewed as one or more rings, one inside the other. For example, as shown in figure (a), a 5 × 5 grid is made of three rings, numbered 1, 2 and 3 (from outside to inside.) A square grid of size N is said to be sorted, if it includes the values from 1 to N^2 in a row-major order, as shown in figure (b) for N = 4. We would like to determine if a given square grid can be sorted by only rotating its rings. For example, the grid in figure (c) can be sorted by rotating the first ring two places counter-clockwise, and rotating the second ring one place in the clockwise direction.

Input

Your program will be tested on one or more test cases. The first input line of a test case is an integer N which is the size of the grid. N input lines will follow, each line made of N integer values specifying the values in the grid in a row-major order. Note than 0

The end of the test cases is identified with a dummy test case with N = 0.

Output

For each test case, output the result on a single line using the following format:

k. result

Where k is the test case number (starting at 1,) and result is "YES" or "NO" (without the double quotes.) and single space between "." and "result".

Sample

Input:
4
9 5 1 2
13 7 11 3
14 6 10 4
15 16 12 8
3
1 2 3
5 6 7
8 9 4
0

Output:
1. YES
2. NO

Added by:psetter
Date:2009-07-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ANARC 2007

hide comments
2010-06-30 03:54:36 Anshu Saurabh
programs submitted in TEXT should be removed.
2010-06-03 21:30:23 Josef Ziegler
Please add some test cases and rejudge the submissions (there are correct .txt submissions).

Last edit: 2010-06-03 21:30:39
2009-11-01 22:26:35 rajeshhamal
I think there is some problem out there. I just wrote a simple code that takes input and then prints wrong answer. Yet it is giving "time limit exceeded".

Re by Blue Mary: cin/cout ACTUALLY will cause TLE. scanf is a very slow input function(even though it's quicker than cin).



Re by rajeshhamal: Yeah i changed the cin's and cout's to scanf and printf, yet it is giving wrong answer in 1.0 sec. (there is no processing involved. Just the input is taken and YES is printed). People have solved it in 0.0 second. I totally don't understand.

Last edit: 2009-11-02 08:03:46
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.