E. Эерэг матриц

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

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

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

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

Чамд $n × n$ хэмжээтэй эерэг матриц байна. Матрицийн мөрүүдийг дээрээс нь доош $1$-с $n$ хүртэл, багануудыг зүүнээс нь баруун тийш $1$-с $n$ хүртэл дугаарлая. $a_{ij}$ нь $i$-р мөр болон $j$-р баганы огтлолцлын элементийг илэрхийлнэ.

$a$ матриц дараах хоёр нөхцлийг хангана:

  • Дурын $i, j$-н ($1 ≤ i, j ≤ n$) хувьд дараах тэнцэтгэл биш үнэн байна: $a_{ij} ≥ 0$;
  • .

Хэрвээ аль ч $i, j$ ($1 ≤ i, j ≤ n$) нь $b_{ij} > 0$ байдаг бол $b$ матриц яг эерэг матриц байна. Эерэг бүхэл $k ≥ 1$ ба $a^{k}$ эерэг матриц байдаг бол түүнийг тодорхойлно.

Оролт

Эхний мөр нь $n$ ($2 ≤ n ≤ 2000$) эерэг бүхэл тоог агуулна. Энэ нь $a$ матрицийн мөр болон баганын тоо юм.

Дараагийн $n$ мөрүүд нь $a$ матрицийн мөрүүдийг тодорхойлно. $i$-р мөр нь $n$ сөрөг биш $a_{i1}, a_{i2}, ..., a_{in}$ ($0 ≤ a_{ij} ≤ 50$) тоог агуулна. байх нь баталгаатай юм.

Гаралт

Эерэг бүхэл $k ≥ 1$ байх $a^{k}$ яг эерэг матриц байдаг бол "$YES$" (хашилтгүйгээр) гэж хэвлэнэ. Эсрэг тохиолдолд "$NO$"(хашилтгүйгээр) гэж хэвлэнэ.

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

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

Оролт
2
1 0
0 1
Гаралт
NO
Оролт
5
4 5 6 1 2
1 2 3 4 5
6 4 1 2 4
1 1 1 1 1
4 4 4 4 4
Гаралт
YES
Сэтгэгдлүүдийг ачааллаж байна...