CF632F Magic Matrix

给定一个 $n \times n$ 的矩阵 $A$。 如果一个元素非负的矩阵满足以下条件，我们称其为“magic”矩阵： - 矩阵是对称的（即 $a_{ij}=a_{ji}$）； - 对于所有 $i$，都有 $a_{ii}=0$； - 对于任意三元组 $i, j, k$（不要求互不相同），都有 $a_{ij} \leq \max(a_{ik}, a_{jk})$。 请判断给定的矩阵 $A$ 是否为 magic 矩阵。 由于输入输出数据量可能非常大，建议使用高效的输入输出方式，例如 C++ 中建议使用 scanf/printf 而非 cin/cout，Java 中建议使用 BufferedReader/PrintWriter 而非 Scanner/System.out。

第一行包含一个整数 $n$（$1 \leq n \leq 2500$），表示矩阵 $A$ 的大小。 接下来的 $n$ 行，每行包含 $n$ 个整数 $a_{ij}$（$0 \leq a_{ij} < 10^9$），表示矩阵 $A$ 的元素。 注意，给定的矩阵不一定是对称的，可以是任意的。

如果给定的矩阵 $A$ 是 magic 的，输出 "MAGIC"（不带引号），否则输出 "NOT MAGIC"（不带引号）。

由 ChatGPT 5 翻译