RELBOARD - Relative Board

Cho một ma trận A với kích thước N*N (2 ≤ N ≤ 1000) chỉ chứa 6 loại giá trị: {-1, -2, 0, 1, 2, 3}

A được gọi là bảng quan hệ của một dãy số T = (T1, T2, ..., Tn), hay T có quan hệ với A nếu:

  • Aij = 0 : Ti = Tj
  • Aij = 1 : Ti < Tj
  • Aij = -1 : Ti > Tj
  • Aij = 2 : Ti ≤ Tj
  • Aij = -2 : Ti ≥ Tj
  • Aij = 3 : Ti khác Tj

Với mọi i, j: 1 <= i, j <= N

Cho bảng quan hệ A, tìm dãy số nguyên dương T = (T1, T2, ..., Tn) có quan hệ với A sao cho Max(T) càng nhỏ càng tốt. Cho rằng dãy số T như vậy luôn tồn tại.

Định nghĩa Max(T) = Max(T1, T2, ..., Tn).

Input

Dòng đầu chứa số nguyên N. N dòng tiếp theo, mỗi dòng chứa N số nguyên mô tả bảng quan hệ A.

Output

Dòng đầu chứa Max(T). Dòng thứ hai chứa N số nguyên dương T1, T2, .., Tn.

Score

Điểm của bạn = 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 

-> Điểm = 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.