题目描述

四色定理是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”

给出一任意地图，试用四种颜色涂色，使相邻区域不能有相同颜色。

输入格式

第一行为$\red{N（1＜N≤26）}$，表示区域数。随后$\red{N}$行描述各区域之间是否相邻。

输出格式

以$\red{1，2，3，4}$分别代表四种颜色，输出各区域的编号（最小字典序）。

样例

输入样例

4

1 2 3 

2 1 4

3 1 4

4 3 2

输出样例

1 2 2 1