RELBOARD - Relative Board

Given a matrix A with dimension N*N (2 ≤ N ≤ 1000) which contains only 6 types of value: {-1, -2, 0, 1, 2, 3}

A is called the relative board of a sequence T = (T1, T2, ..., Tn), or T relates to A if:

  • Aij = 0 : Ti = Tj
  • Aij = 1 : Ti < Tj
  • Aij = -1 : Ti > Tj
  • Aij = 2 : Ti ≤ Tj
  • Aij = -2 : Ti ≥ Tj
  • Aij = 3 : Ti is not equal to Tj

For all i, j: 1 <= i, j <= N

Given the relative board A, find the sequence of positive integers T = (T1, T2, ..., Tn) that relates to A such that Max(T) is as small as possible. Suppose that the sequence T always exists.

Define Max(T) = Max(T1, T2, ..., Tn).

Input

The first line contains an integer N. N lines follow, each line contains N integers that describe the relative board A.

Output

The first line contains Max(T). The second line contains N separated positive integers T1, T2, .., Tn.

Score

Your score = Max(T).

Example

Input:
6
 0  1  1  1  2  2
-2  0  1  0  2  2
-2 -1  0  3  0  1
-2 -2  3  0  1  1
-1 -2  0 -1  0  1
-1 -2 -1 -1 -1  0

Output:
4
1 2 3 2 3 4 

-> Score = 4

Added by:Race with time
Date:2009-04-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:Mr. Lê Minh Hoàng

hide comments
2011-02-06 14:19:44 Race with time
I think it's because there are several test cases and the score is the average of them.
2011-01-18 16:02:39 kritivasas
can i get one more test case?
2010-12-30 16:51:59 Pinco Pallino
How is possible that some scores are not integer?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.