B. Шинэ жилийн сэлгэмэл

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

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

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

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

Codeforces-н гишүүн ainta-д $p_{1}, p_{2}, ..., p_{n}$ сэлгэмэл байна. Шинэ жил болох гэж байгаа тул тэр өөрийн сэлгэмэлээ аль болох хөөрхөн болгохыг хүсэж байгаа юм.

Хэрвээ $a_{1} = b_{1}, a_{2} = b_{2}, ..., a_{k - 1} = b_{k - 1}$ ба $a_{k} < b_{k}$ нөхцлийг хангадаг $k$ ($1 ≤ k ≤ n$) бүхэл тоо байгаа бол $a_{1}, a_{2}, ..., a_{n}$ сэлгэмэл нь $b_{1}, b_{2}, ..., b_{n}$ сэлгэмэлээс илүү хөөрхөн юм.

$p$ сэлгэмэл нь зөвхөн хоёр ялгаатай элементүүдийг сольж өөрчилж болох тийм эмзэг юм. Гэхдээ хоёр элементийг солих нь таны бодож байгаагаас илүү хэцүү байна. $n × n$ хэмжээтэй $A$ матриц өгөгдсөн ба хэрвээ $A_{i, j} = 1$ бол хэрэглэгч айнта $p_{i}$ ба $p_{j}$ ($1 ≤ i, j ≤ n$, $i ≠ j$) утгуудыг сольж чадна.

$p$ сэлгэмэл болон $A$ матриц өгөгдсөн ба Codefores-н гишүүн ainta өөрийн гарган авч чадах хамгийн хөөрхөн сэлгэмлийг мэдэхийг хүсэж байна.

Оролт

Эхний мөр нь $p$ сэлгэмэлийн хэмжээ болох $n$ ($1 ≤ n ≤ 300$) бүхэл тоог агуулна.

Хоёр дахь мөр нь ainta-д байгаа $p$ сэлгэмэл болох зайгаар тусгаарлагдсан $n$ ширхэг $p_{1}, p_{2}, ..., p_{n}$ бүхэл тоонуудыг агуулна. $1$-ээс $n$-н хоорондох бүхэл тоо бүр нь тухайн сэлгэмэлд яг нэг удаа орсон байна.

Дараагийн $n$ мөрүүдэд $A$ матриц байна. $i$-р мөр нь "0" эсвэл "1" гэсэн $n$ ширхэг тэмдэгтүүд агуулах ба энэ нь $A$ матрицын $i$-р мөрийн тодорхойлолт юм. $i$-р мөрийн $j$-р тэмдэгт $A_{i, j}$ нь $i$-р мөр болон $j$-р баганы огтлолцол дээрх элемент юм. Бүх $i, j$ бүхэл тоонуудын хувьд $1 ≤ i < j ≤ n$, $A_{i, j} = A_{j, i}$ байна. Мөн бүх $i$ бүхэл тоонуудын хувьд $1 ≤ i ≤ n$, $A_{i, i} = 0$ байна.

Гаралт

Авч болох хамгийн хөөрхөн сэлгэмэлийг илэрхийлэх зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоонууд агуулсан нэг л мөр хэвлэнэ.

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

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

Оролт
7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000
Гаралт
1 2 4 3 6 7 5
Оролт
5
4 2 1 5 3
00100
00011
10010
01101
01010
Гаралт
1 2 3 4 5

Тэмдэглэл

Нэгдүгээр жишээнд боломжит хамгийн хөөрхөн сэлгэмлийг авахын тулд хийх хэрэгтэй солилт бол: $(p_{1}, p_{7})$.

Хоёрдугаар жишээнд боломжит хамгийн хөөрхөн сэлгэмлийг авахын тулд хийх хэрэгтэй солилт бол: $(p_{1}, p_{3}), (p_{4}, p_{5}), (p_{3}, p_{4})$.

Тус бүр нь $n$-с хэтрэхгүй $n$ ширхэг ялгаатай эерэг бүхэл тоонуудаас бүрдсэн $p_{1}, p_{2}, ..., p_{n}$ бүхэл тоонуудын дараалал бол $p$ сэлгэмэл юм. $p_{i}$ нь $p$ сэлгэмэлийн $i$-р элементийг илэрхийлнэ. $n$ нь $p$ сэлгэмэлийн хэмжээг илэрхийлнэ.

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