← 返回题目列表

Codeforces · 632/F

F. 魔法矩阵

中文机器翻译题面 查看原题

给定一个大小为 n × n 的矩阵 A。

如果具有非负元素的矩阵是对称的(因此 aij = aji)、aii = 0 且对于所有三元组 i、j、k,aij ≤ max(aik, ajk),我们将其称为 magic。请注意,i、j、k 不需要不同。

确定矩阵是否是魔法矩阵。

由于输入/输出可能达到非常大的尺寸,建议使用快速输入/输出方法:例如,在C++中更喜欢使用scanf/printf而不是cin/cout,在Java中更喜欢使用BufferedReader/PrintWriter而不是Scanner/System.out。

输入

第一行包含整数 n (1 ≤ n ≤ 2500) — 矩阵 A 的大小。

接下来的 n 行中的每一行都包含 n 个整数 aij (0 ≤ aij < 109) — 矩阵 A 的元素。

请注意,给定的矩阵不一定是对称的,并且可以是任意的。

输出

如果给定矩阵 A 是 magic,则打印“MAGIC”(不带引号)。否则打印“NOT MAGIC”。

示例

输入 #1

3
0 1 2
1 0 2
2 2 0

输出 #1

MAGIC

输入 #2

2
0 1
2 3

输出 #2

NOT MAGIC

输入 #3

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

输出 #3

NOT MAGIC