暂无测试数据。

Background

Special for beginners, ^_^

Description

编程验证四色原理。
如图9.10-3所示，表示一个地图有6个地区,它对应着一个6x6的邻接矩阵(见输出样例).输出一种合理的着色方案，要求任意两个相邻的地区都不能同色。

Format

Input

第1行为n,表示地区个数,n≤20。
以下为nxn的邻接矩阵，a[i.j]=0表示地区i与地区j不相邻，a[i.j]-1表示地区i与地区j相邻。

Output

一行n个数,表示一种这色方案,每两个数之间用一个空格隔开。
答案不唯一,输出任意一个解即可。

Sample 1

Input

6
0 1 0 1 0 1 
1 0 1 1 0 0 
0 1 0 1 0 0
1 1 1 0 1 1
0 0 0 1 0 1 
1 0 0 1 1 0

Output

1 2 1 3 4 2

Limitation

1s, 64MB for each test case.

Source

Vijos Original