5493: 星战（star）

最近小项的班级里流行一款推理谜题——星战（Star Battle）。它的规则如下：

在一个n行n列的网格中，网格被划分成n个不同的区域，你需要在网格上放置n个星星，不过它们有一些限制。

1. 每个区域内只能放置一颗星星。

1. 每个区域内只能放置一颗星星。

2. 任意两个星星不能位于网格的同一行、同一列。

3. 任意两个星星不能水平、垂直、对角线相邻。

小项是你的表弟，由于他把纸面的谜题变成程序的输入、以及把程序输出结果画在纸面上需要114.514秒，他希望你能开发一款程序，需要你的程序在1秒内得出星战谜题的解，并且先输出行号小的，后输出行号大的，如果有多组解，尽量使得前面行的星星的列号尽可能的小。你可以帮帮他吗？

从文件star.in中读取数据。

第一行一个数字n。

接着n行，每行n个数字，a_{i,j}表示第i行第j列的网格属于a_{i,j}个区域。

输出文件到star.out中。

如果谜题有解，则输出包含n行，每行两个数字，第i行表示第i行的星星所在的行号和列号。如果没有解，输出-1即可。

5
1 1 1 1 1
1 1 1 2 3
4 5 5 2 3
4 4 2 2 3
4 3 3 3 3

1 3
2 5
3 2
4 4
5 1