E. Маргаан

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

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

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

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

Алекс, Боб хоёр найзууд бөгөөд Бертаунд амьдардаг. Энэ хотод $n$ замын уулзвар байдаг ба эдгээрийн зарим нь хос чиглэлтэй ижил урттай замуудаар холбогдоно. Бобын гэр $1$ дугаартай уулзвар дээр, Алексынх $n$ дугаартай уулзвар дээр байдаг.

Нэг удаа Алекс, Боб хоёр ноцтой маргаж тэр цагаас хойш хоорондоо уулзахаас зайлсхийх болов. Өнөөдөр Боб өөрийн байшингаасаа $n$ дугаартай уулзварт, харин Алекс гэрээсээ $1$ дугаартай уулзварт очих хэрэгтэй болсон. Тэд ямар ч уулзвар дээр нэг дор тааралдахыг хүсэхгүй байгаа боловч гудамжны голд зөрөхийг юман чинээ тоохгүй байж чадахаар байв. (Эхний жишээг харна уу).

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

Залуус тасралтгүй явах ба ижил хурдтай явна. Өөрөөр хэлбэл нэг нь нэг уулзварт ирж байхад нөгөө нь энэ уулзварыг орхин явж байж болно. Жишээлбэл Боб $2$ дугаартай уулзвараас $3$ дугаартай уулзвар руу явж байхад Алекс $1$ дугаартай уулзвараас $2$ дугаартай уулзвар руу явж байж болно.

Хэрвээ шаардлагатай маршрутууд байхгүй бол таны програм "-1" гэж хэвлэх ёстой.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 500, 1 ≤ m ≤ 10000$) байх буюу уулзвар болон замуудын тоо байна. Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга байх ба уг замаар холбогдсон уулзваруудын дугаар байна. Ямар ч зам уулзварыг өөртэй нь холбохгүй ба ямар ч хоёр уулзвар хоорондоо нэгээс олон замаар холбогдохгүй.

Гаралт

Хэрвээ шаардлагатай маршрутууд байхгүй бол "-1" гэж хэвлэ. Бусад тохиолдолд эхний мөрөнд хамгийн богино маршрутуудын урт $k$ (маршрутын урт нь үүнд байгаа замуудын тоо байна) байна. Дараагийн мөрөнд $k + 1$ бүхэл тоон утга байх буюу Бобын явж өнгөрөх замуудын дугаарыг агуулсан маршрут байна. Хамгийн сүүлийн мөрөнд Алексийн маршрут ижил форматтайгаар байна. Хэрвээ хэд хэдэн боломжит шийдэл байвал алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

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

Оролт
2 1
1 2
Гаралт
1
1 2 
2 1 
Оролт
7 5
1 2
2 7
7 6
2 3
3 4
Гаралт
-1
Оролт
7 6
1 2
2 7
7 6
2 3
3 4
1 5
Гаралт
6
1 2 3 4 3 2 7 
7 6 7 2 1 5 1 
Сэтгэгдлүүдийг ачааллаж байна...