D. Өтөн байшин

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

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

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

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

Арние өт алиман байшингаа идэж дуусаад дахин хөдлөхөөр шийджээ. Тэрээр өөрийн оюун ухаандаа төлөвлөгөөгөө боловсруулсан бөгөөд өрөөнүүдийн байрлал болон тэдгээр нь хэрхэн коридоруудаар холбогдсон болох нь мэдэгдэж байв. Тэрээр бүх өрөөнүүдийг $1$-ээс $n$ хүртэл дугаарласан бөгөөд бүх коридорууд нь 2 чиглэлтэй байх юм.

Арние шинэ байшингаа өөрийн хуучин байшинтайгаа яг ижилхэн харагдуулахыг хүсжээ. Иймд уг байшин нь яг $n$ ширхэг өрөөтэй байх ёстой ба хэрэв хуучин байшинд $i$-р өрөөнөөс $j$-р өрөө хүртэлх коридор оршин байсан бол уг коридорыг шинэ байшинд барих ёстой юм.

Байшинг барих явцад Арние алимыг ямар нэгэн өрөөнөөс эхлэн идэж эхлэх бөгөөд өөрийн замаар идсээр бүх коридоруудаар дамжин идэж эхэлсэн өрөөндөө ирмэгцээ зогсох ажээ. Мөн түүнчлэн Арние зогсолтгүй идэх юм. Өөрөөр хэлбэл шинэ байшинг байгуулж дуусах хүртлээ Арние хугацааны мөч болгонд шинэ коридор үүсгэн мэрсээр байх бөгөөд тэрээр аль хэдийн үүсгэсэн коридорын дагуу явахгүй байх юм.

Тэгсэн хэдий ч байшинг өөрчлөх болгондоо нэг ижил дарааллаар коридоруудыг үүсгэнэ гэдэг нь үнэхээр хүнд ажил юм. Иймд Арние өмнөх байшинд коридорууд нь хэрхэн байрласан дарааллыг мэдэж байгаа ч гэсэн шинэ байшингаа барихдаа өөр дарааллаар коридор үүсгэн мэрэхийг хүсжээ. Коридор үүсгэх дараалал нь дайран өнгөрөх ёстой өрөөнүүдийн дарааллын бүртгэл хэлбэртэйгээр дүрслэгдэх юм. Харин бидний үүсгэх шинэ бүртгэл нь хэл зүйн хувьд хамгийн бага нь байх ёстой боловч энэ бүртгэл нь өмнөх байшингийн бүртгэлээс хэл зүйн хувьд эрс их байх ёстой байв. Арние-д тусална уу.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($3 ≤ n ≤ 100, 3 ≤ m ≤ 2000$) өгөгдөнө. Эдгээр нь харгалзан Арние-ын байшингийн өрөөний тоо болон коридорын тоог илэрхийлнэ. Дараагийн мөрөнд $m + 1$ ширхэг эерэг бүхэл тоонууд өгөгдөх ба эдгээр нь бүгд $n$-ээс хэтрэхгүй байна. Эдгээр бүхэл тоонууд нь Арние-ын хуучин байшиндаа коридор үүсгэхдээ явсан замыг илэрхийлэх бөгөөд мэрэх явцдаа дайран өнгөрсөн өрөөнүүдийн бүртгэл хэлбэртэйгээр өгөгдсөн байна. Түүнчлэн уг бүртгэлийн эхний болон сүүлийн тоо нь давхцаж байх юм.

Уг бүртгэл дэх эхний өрөө нь байшингийн орох хаалга байх бөгөөд ийм учраас Арние уг өрөөнөөс эхлэн мэрэх ёстой юм.

Та өөртэйгөө холбогдох ямар ч өрөө байхгүй гэж үзэх ба дурын хос өрөөнүүдийн хооронд хамгийн ихдээ 1 коридор оршин байна гэж үзнэ үү. Мөн бусад өрөөнүүдээсээ тусгаарлагдсан хэсэг өрөөнүүд байх боломжтой.

Гаралт

$n$-ээс хэтрэхгүй $m + 1$ ширхэг эерэг бүхэл тоо хэвлэнэ үү. Эдгээр тоонууд нь Арние өөрийн шинэ байшингаа хэрхэн мэрж үүсгэхийг илэрхийлэх шинэ замын тайлбар байх юм. Хэрэв шинэ зам олох боломжгүй байвал та No solution гэж хэвлэнэ үү. Мөн түүнчлэн таны хариултын эхний тоо нь сүүлийн тоотойгоо тэнцүү байх ёстой бөгөөд уг эхний тоо нь байшингийн орох хаалга байх ёстойг анхаарна уу.

Орчуулсан: Баатархүү

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

Оролт
3 3
1 2 3 1
Гаралт
1 3 2 1 
Оролт
3 3
1 3 2 1
Гаралт
No solution
Сэтгэгдлүүдийг ачааллаж байна...