Грэгд $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$-р тоотой тэнцэх ёстой.