#6802. L2-2 远古大陆

L2-2 远古大陆

Description

在一个神秘的大陆上,有许多部落、危险的丛林和安全的道路,大陆外面是无尽的海洋无法进入

每个部落都有自己的语言和文化,只能与互通的部落进行交流

危险的丛林是不能够通过的,部落和安全的道路都能够通过

请按字典序输出大陆上能够互相交流的部落编号

大陆上的六边形区域呈蜂窝状的,类似下图:

Format

Input

第一行输入一个数n,代表n*n大小的大陆

后面n行每行n个数,0代表危险的丛林,1代表安全的道路,2、3、4、...、X代表部落编号

由于六边形地图的特殊性,第奇数行是稍微偏左的,具体可见样例解释

Output

输出若干行

每行输出从小到大的能够交流的部落编号,且每一行第一个数也是从到大递增的

Samples

5
1 0 0 0 1 
2 0 0 3 0 
0 0 1 1 0 
4 0 5 0 0 
6 7 8 0 1 

2 
3 4 5 6 7 8 

样例解释:

样例地图实际上是这样:

image

可以发现每个点周围最多有6个邻点

2号部落与其他部落没法交流所以第一行直接输出2

3号与5号交流,5号和8号可以交流,8号可以跟7号交流,7号可以跟4号和6号交流,所以输出 3 4 5 6 7 8

数据范围

数据占比 范围
对于前20%数据 1<=n<=50
对于前50%数据 1<=n<=500
对于前100%数据 1<=n<=2000

对于所有数据保证部落编号不超过1e7

对于前50%的每个数据为2分,后50%的每个数据为3分

Limitation

1s, 1024KiB for each test case.