B. Грэг ба граф

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

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

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

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

Грэгд $n$ ширхэг оройноос тогтсон чиглэлтэй жинтэй граф байв. Графын орой бүр хоорондоо холбогдсон бөгөөд хоёр чиглэлтэй байна. Грэгд графаар тоглох таалагддаг тул ээлжит тоглоомоо зохиов:

  • Тоглоом $n$ үеэс тогтоно.

  • $i$-р үед ирэхэд Грэг $x_i$ дугаартай оройг графаас устгана. Оройг устгахад түүнээс гарж, орж байсан бүх ирмэгүүдийг бас устгана.

  • Үе бүрийн өмнө үйлдэл хийхээсээ өмнө Грэг бүх хос оройнуудыг холбосон хамгийн богино замуудын нийт уртыг мэдэхийг хүсжээ. Өөрөөр хэлбэл $v$-гээс $u$-рүү очих хамгийн богино замын урт нь $d(i, v, u)$ гэж үзвэл Грэг дараах нийлбэрийг мэдэхийг хүсэж байна: $\sum\limits_{v,u\ (v \neq u)} d(i, v, u)$.

Грэгд дээрх нийлбэрийг олохын тулд алхам бүр дээр нь туслаарай.

Оролт

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

Дараагийн $n$ мөрөнд матриц хэлбэрээр өгөгдсөн графын тодорхойлолт байх бөгөөд $i$-р мөрний $j$-р тоо нь $a_{ij}$ ($1 ≤ a_{ij} ≤ 10^5, a_{ii} = 0$) байна гэдэг нь $i$-р оройноос $j$-р орой руу чиглэсэн ирмэгийн жин юм.

Дараагийн мөрөнд Грэгийн устгасан оройнуудын дугаар болох давтагдаагүй $n$ ширхэг бүхэл тоо өгөгдөнө: $x_1, x_2, ..., x_n$ $(1 ≤ x_i ≤ n)$

Гаралт

$n$ бүхэл тоо хэвлэнэ үү. $i$-р үйлдэл хийхийн өмнөх замуудын уртын нийлбэр нь $i$-р тоотой тэнцэх ёстой.

Орчуулсан: Баттулга

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

Оролт
1
0
1
Гаралт
0 
Оролт
2
0 5
4 0
1 2
Гаралт
9 0 
Оролт
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3
Гаралт
17 23 404 0 
Сэтгэгдлүүдийг ачааллаж байна...