Сиел үнэг програмчлалын тэмцээнд зориулж бодлого зохиожээ. Тэр нь "Танд бүх ирмэгүүд нь нэгж урттай $n$ ширхэг орой бүхий чиглэлгүй граф өгөгдсөн бол 1-р оройноос 2-р орой хүрэх хамгийн богино замын тоог олно уу" гэсэн бодлого юм.

Бусад зохиогчдын нэгэн адил, тэрээр өөрийнхөө төрсөн өдөр ч юм уу, найз залуугийнхаа дугаар ч юм уу тодорхой гаралт бүхий жишээ зохиомоор санагджээ. Бодлогын хариу яг $k$ байх тест жишээ хийхэд нь та туслаж чадах уу?

Оролт

$k$ гэсэн ганц тоо агуулсан нэг мөр өгөгдөнө. $(1 \leq k \leq 10^9)$.

Гаралт

$n$ ширхэг $(2 \leq n \leq 1000)$ оройтой $G$ графыг хэвлэнэ үү. $1$-р оройноос $2$-р орой хүрдэг яг $k$ ширхэг ялгаатай хамгийн богино зам байх ёстой.

Эхний мөрөнд нэг тоо $n$ байна. Түүний дараа $n$ ширхэг мөр, $n$ ширхэг багана бүхий граф $G$-н зэргэлдээ матриц байна. Матрицийн бүх элемент нь 'N' эсвэл 'Y' байна. Хэрэв $G_{ij}$ нь 'Y' бол граф $G$-д $i$ болон $j$ дугаар оройг холбосон ирмэг байна гэсэн үг. Графын оройг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.

Граф нь чиглэлгүй, энгийн байх шаардлагатай. Ө.х. $G_{ii}$='N' ба $G_{ij}=G_{ji}$ гэсэн үг. Мөн 1-р оройноос 2-р орой хүрэх ядаж нэг зам байх хэрэгтэй. Бодлогын хариу заавал олдох нь баталгаатай. Ялгаатай зөв хариу байвал алийг нь ч хэвлэж болно.

Эхний жишээнд, 1-3-2 ба 1-4-2 гэсэн хамгийн богино зам $2$ ширхэг байна.

Хоёрдугаар жишээнд, 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2 гэсэн хамгийн богино зам $9$ ширхэг байна.