拯救末日

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

  2012年12月21日,世界末日,所有的人都像往常一样做着自己的工作,sdut的ACMer在实验室里埋头敲代码,就在这时,ACMer收到了一封信,信中的内容是这样的:

  亲爱的ACMer:

  我是爱神丘比特,今天不是传说中的世界末日,而是真正的世界末日,天帝将拯救苍生的使命交给了我,他送了我一张地图,这张地图是个迷宫,如下图所示:

如图:

横坐标从0到N,纵坐标从0到N。在这个迷宫里1代表墙,不能通行,0代表空地,可以通行,但是由于n太大了(N<=1000000),我的法力有限没有办法携带这么大的迷宫,所以热心的ACMer 请帮我把这张地图缩到最小:只能缩小空地,如图,只可以将第二列和第三列合并,如下图:

此图就为最简地图,我只能从(0,0)出发,如果到达(n,n)那么就可以拯救世界,由于世界末日的影响,我只能向下,向右走。

 

 

Input

 多组输入。
第一行输入N(n<=1000000)和M(m<=1000)
N代表N*N(包括0)的迷宫,M代表墙的个数。
接下来M行,每行输入i,j代表墙的位置。

Output

 如果能够拯救世界,输出最简的地图;如果不能输出-1。

Sample Input

10 5
6 6
1 1
8 1
4 10
4 7

Sample Output

0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
0 0 0 0 0 0 0 
0 0 0 0 1 0 1 
0 0 0 0 0 0 0 
0 0 0 1 0 0 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
0 0 0 0 0 0 0

Hint

 

Source

WL