601A орчуулах · Codeforces.mn

# Хоёр маршрут
Абсурдистан $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$-г хэвлэ.

## Тэмдэглэл
Эхний жишээн дээр галт тэрэг дараах маршрутаар явж болох ба
 ![](http://codeforces.com/predownloaded/45/30/45307ea441d2996b4e3db04de8169f6600202297.png) автобус дараах маршрутаар явж болно ![](http://codeforces.com/predownloaded/17/34/17348a86f2090cbcfe747091924a85e6176e16c0.png). Тэд $4$-р хотод ижил цагт ирнэ.

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

-- Г.Мэндбаяр

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

Оролт

4 2
1 3
3 4

Гаралт

Оролт

Гаралт

-1

Оролт