D. Design Tutorial: Урвуу бодлого

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

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

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

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

"Урвуу бодлого" нэртэй нэгэн аргаар буюу байгаа бодлогыг хойноос нь урвуулах байдлаар шинэ бодлого зохиож болдог.

Тодорхой хэлбэл, бид анхны бодлогын гаралтыг өгөөд оролтыг асууна, тэгээд анхны бодлогын код руу оролтоо хийгээд гаралтыг нь тулгаж шалгана. Topcoder Open 2014 Round 2C-н хүнд түвшний бодлого InverseRMQ бол үүний нэг жишээ.

Одоо ийм аргаар бодлого зохиож үзье. Ашиглах бодлого маань:

"Танд мод өгөгдсөн бөгөөд түүний аль ч хос зангилаануудын хоорондох зайг тооцоол."

Тиймээ энэ үнэхээр амархан, гэхдээ урвуу хувилбар нь арай хүнд: танд $n × n$ зайн матриц (матрицын нүднүүд оройнуудын хоорондох зайг илэрхийлнэ) өгөгдсөн байна. Энэ нь жинтэй модны (бүх жин нь эерэг бүхэл тоо байна) зайн матриц мөн эсэхийг тодорхойл.

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 2000$) бүхэл тоог агуулна. Энэ бол графын зангилаануудын тоо.

Дараагийн $n$ мөр бүр нь $n$ ширхэг бүхэл $d_{i, j}$ ($0 ≤ d_{i, j} ≤ 10^{9}$) тоонууд агуулна. Энэ нь $i$ болон $j$-р зангилаануудын хоорондох зай.

Гаралт

Хэрвээ мод байгаа бол гаралт "YES" байна, эсрэг тохиолдолд гаралт "NO" байна.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3
0 2 7
2 0 9
7 9 0
Гаралт
YES
Оролт
3
1 2 7
2 0 9
7 9 0
Гаралт
NO
Оролт
3
0 2 2
7 0 9
7 9 0
Гаралт
NO
Оролт
3
0 1 1
1 0 1
1 1 0
Гаралт
NO
Оролт
2
0 0
0 0
Гаралт
NO

Тэмдэглэл

Эхний жишээнд шаардсан мод байна. $1$ ба $2$ зангилаануудын хооронд $2$ жинтэй нэг ирмэг байна, $1$ ба $3$ зангилаануудын хооронд $7$ жинтэй өөр нэг ирмэг байна.

Хоёр дахь жишээнд энэ боломжгүй, учир нь $d_{1, 1}$ нь $0$ байх ёстой гэвч $1$ байна.

Гурав дахь жишээнд энэ боломжгүй, учир нь $d_{1, 2}$ нь $d_{2, 1}$-тэй тэнцүү байх ёстой.

Сэтгэгдлүүдийг ачааллаж байна...