Magic Matrix

定义一个大小为 $n\times n$ 矩阵 $a$ 为魔法矩阵，当且仅当 $a$ 满足以下条件: 以下 $i,j,k\in \mathbb{Z^+}$ + $\forall i\in[1,n],a_{i,i}=0$ + $\forall i,j\in[1,n],a_{i,j}=a_{j,i}$ + $\forall i,j,k\in[1,n],a_{i,j}\le\max(a_{i,k},a_{j,k})$ 给你一个矩阵，问它是不是魔法矩阵。 如果 $a$ 是魔法矩阵输出 $\texttt{MAGIC}$，否则输出 $\texttt{NOT MAGIC}$，可以参见样例。 $1\leq n\leq 2500,\forall i,j\in[1,n],0\le a_{i,j}\le 10^9$

You're given a matrix $ A $ of size $ n×n $ . Let's call the matrix with nonnegative elements magic if it is symmetric (so $ a_{ij}=a_{ji} $ ), $ a_{ii}=0 $ and $ a_{ij}<=max(a_{ik},a_{jk}) $ for all triples $ i,j,k $ . Note that $ i,j,k $ do not need to be distinct. Determine if the matrix is magic. As the input/output can reach very huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

The first line contains integer $ n $ ( $ 1<=n<=2500 $ ) — the size of the matrix $ A $ . Each of the next $ n $ lines contains $ n $ integers $ a_{ij} $ ( $ 0<=a_{ij}&lt;10^{9} $ ) — the elements of the matrix $ A $ . Note that the given matrix not necessarily is symmetric and can be arbitrary.

Print ''MAGIC" (without quotes) if the given matrix $ A $ is magic. Otherwise print ''NOT MAGIC".

3
0 1 2
1 0 2
2 2 0

MAGIC

2
0 1
2 3

NOT MAGIC

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

NOT MAGIC