F. Шидэт матриц

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n × n$ хэмжээтэй $A$ матриц өгөгдсөн.

Хэрвээ матриц нь сөрөг биш элементүүдтэй ба бүх $i, j, k$ гурвалын хувьд тэгш хэмтэй (буюу $a_{ij} = a_{ji}$), $a_{ii} = 0$ and $a_{ij} ≤ max(a_{ik}, a_{jk})$ байвал энэ матрицыг шидэт матриц гэнэ.

Матрицыг шидэт мөн эсэхийг тодорхойл.

Оролт гаралт нь маш их хэмжээтэй байж болох тул оролт гаралтын хурдан функцүүдийг ашиглана уу. Жишээ нь: C++ хэлэнд "cin/cout"-ийн оронд "scanf/printf"-ийг ашиглах, $Java$ хэлэнд "Scanner/System.out"-ийн оронд "BufferedReader/PrintWriter"-ийг ашиглана уу.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 2500$) байх ба энэ нь $A$ матрицын хэмжээ юм.

Дараагийн $n$ ширхэг мөр бүрт $n$ ширхэг бүхэл тоон утга $a_{ij}$ ($0 ≤ a_{ij} < 10^{9}$) байх ба $A$ матрицын элементүүд юм.

Өгөгдсөн матриц нь заавал тэгш хэмтэй байх албагүй ба санамсаргүйгээр үүсгэгдсэн ч байж болно.

Гаралт

Хэрвээ өгөгдсөн матриц $A$ нь шидэт матриц байвал "MAGIC" гэж хэвлэ. Бусад тохиолдолд "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
Сэтгэгдлүүдийг ачааллаж байна...