你是一名冒险家,目前正在一座邪恶的神庙中旅行。击败几只弱小的僵尸后,你到达了一个由瓷砖组成 n × n 网格的方形房间。行从上到下编号为 1 到 n,列从左到右编号为 1 到 n。房间的另一边有一扇被邪恶魔法力量锁着的门。门上刻有以下铭文:
清洗一切邪恶将唤醒之门!
作为一名非常资深的冒险家,你立即意识到这意味着什么。您注意到网格中的每个单元格最初都是邪恶的。您应该纯化所有这些细胞。
你所知道的唯一净化瓷砖的方法是施展“净化”法术。你在单个图块上施放这个法术——然后,与所选图块位于同一行和同一列的所有单元格都会被净化(包括所选图块)!允许多次纯化细胞。
你想净化所有 n × n 个细胞,同时尽量减少施展“净化”法术的次数。这听起来很简单,但您刚刚注意到有些瓷砖比其他瓷砖特别邪恶。你不能对那些特别邪恶的瓷砖施放“净化”法术,即使它们被净化后也是如此。如果共享同一行或同一列的单元格被“净化”咒语选中,它们仍然可以被净化。
请找到某种方法以最少的施法次数净化所有细胞。如果没有这样的方法,则打印-1。
输入
第一行将包含一个整数 n (1 ≤ n ≤ 100)。然后,接下来有 n 行,每行包含 n 个字符。第 i 行中的第 j 个字符表示位于第 i 行 j 列的单元格。如果它是一个特别更邪恶的单元格,它将是字符“E”,并且“.”。否则。
输出
如果无法纯化所有细胞,则输出-1。否则,如果您的解决方案施放 x 个“净化”法术(其中 x 是可能的最小法术数),则输出 x 行。每行应包含两个整数,表示您应对其施放“净化”咒语的单元格的行号和列号。
示例
输入 #1
3 .E. E.E .E.
输出 #1
1 1 2 2 3 3
输入 #2
3 EEE E.. E.E
输出 #2
-1
输入 #3
5 EE.EE E.EE. E...E .EE.E EE.EE
输出 #3
3 3 1 3 2 2 4 4 5 3
注意
第一示例说明如下。紫色瓦片是尚未净化的邪恶瓦片。红色瓷砖是施放“净化”的瓷砖。黄色瓷砖是由于当前“净化”法术而被净化的瓷砖。绿色瓷砖是之前经过净化处理的瓷砖。
在第二个示例中,无法纯化位于第 1 行第 1 列的单元格。
对于第三个示例: