题目描述

一张平面地图有 $n$ 个地区，给出地区相邻关系。使用编号为1至4的四种颜色，为每个地区涂一种颜色，使相邻地区颜色不同。

输入格式

第一行 $n$。接下来 $n$ 行，每行 $n$ 个0或1，表示相邻矩阵。矩阵对称，对角线为0；数据保证对应平面图且存在合法四染色。

输出格式

输出 $n$ 个1至4之间的整数，依次为各地区颜色。任意合法方案均可。

样例

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

2 3 2 1 2 3

数据范围

$1\le n\le20$。