A. Хоёр маршрут

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

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

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

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

Абсурдистан $n$ хоттой ($1$-с $n$ хүртэл дугаарлагдсан) ба $m$ хос чиглэлтэй төмөр замтай. Энд бас инээд хүрмээр энгийн замын сүлжээ - ялгаатай $x$ болон $y$ хот бүрийн хувьд уг хоёр хотыг холбосон төмөр зам байхгүй тохиолдолд л $x$ болон $y$ хотуудын хооронд хос чиглэлтэй авто зам байдаг. Өөр хотуудруу аялахад нэг төмөр зам эсвэл нэг авто замыг ашигладаг ба яг нэг цаг явдаг.

Галт тэрэг, автобус хоёр $1$ дугаартай хотыг зэрэг орхино. Тэдэнд ижил эцсийн зогсоол болох $n$ хот байх ба замдаа ямар ч зогсолт хийхгүй (гэвч тэд $n$ хотод хүлээж болно). Галт тэрэг зөвхөн төмөр замаар явах бол автобус зөвхөн авто замаар явна.

Танд тээврийн хэрэгсэл бүрт зориулсан маршрутын төлөвлөгөө гаргах даалгавар өгөгдсөн ба маршрут бүр ямар ч зам болон төмөр замыг хэдэн ч удаа ашиглаж болно. Аюулгүй гэж үзэх чухал үзэл бодлуудын нэг нь төмөр замын огтлолцол дээрх ослоос зайлсхийх зорилгоор галт тэрэг болон автобус нэг хотод ($n$ хотоос бусад хотод) зэрэг ирж болохгүй.

Эдгээр хязгаарлалтуудын дор хоёр тээврийн хэрэгсэл хоёул $n$ хотод хүрэх хамгийн бага цагийн тоо хэд вэ(автобус болон галт тэрэгний ирэх цагийн хамгийн их нь хэд вэ)? Автобус, галт тэрэг хоёр $n$ хотод ижил цагт ирэх шаардлагагүй боловч ижил цагт ирж болно.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 400$, $0 ≤ m ≤ n(n - 1) / 2$) байх ба харгалзан хотуудын тоо болон төмөр замын тоо.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $u$ ба $v$ байх ба $u$ болон $v$ ($1 ≤ u, v ≤ n$, $u ≠ v$) хотуудын хоорондох төмөр замыг заана.

Дурын хоёр хотыг хамгийн ихдээ нэг төмөр зам холбоно гэж төсөөлөөрэй.

Гаралт

Тээврийн хэрэгслүүд $n$ хотод хамгийн багадаа хэдэн цагийн дараа ирэхийг илтгэх бүхэл тоон утгыг хэвлэ. Ядаж нэг тээврийн хэрэгсэл $n$ хотод ирэх боломжгүй бол $ - 1$-г хэвлэ.

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

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

Оролт
4 2
1 3
3 4
Гаралт
2
Оролт
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Гаралт
-1
Оролт
5 5
4 2
3 5
4 5
5 1
1 2
Гаралт
3

Тэмдэглэл

Эхний жишээн дээр галт тэрэг дараах маршрутаар явж болох ба автобус дараах маршрутаар явж болно . Тэд $4$-р хотод ижил цагт ирнэ.

Хоёр дахь жишээн дээр Абёурдистан төмөр замчдаар зохицуулагдана. Энд ямар ч авто зам байхгүй ба автобусанд $4$ хотод хүрэх зам байхгүй.

Сэтгэгдлүүдийг ачааллаж байна...