D. Роботын удирдлага

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

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

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

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

Роботын Компаний босс бол хэрцгий хүн. Түүний уриа бол "Урагш яв эсвэл Үх!". Мөн энэ нь түүний компаний бүтээгдэхүүнүүдийн яг хийдэг зүйл нь юм. Компаний роботын чиглэлтэй граф дотор явах шинжийг харцгаая. Энэ шинж нь "Роботын Гурван Хууль" нэртэй.

  • Хууль 1. Робот өөрийн аль хэдийн зочилчихсон графын оройд дахин ирвэл өөрийгөө устгана.
  • Хууль 2. Робот явах замгүй болсон (оройгоос гарсан ирмэггүй орой дээр очих үедээ) үедээ өөрийгөө устгана.
  • Хууль 3. Роботод явах хэд хэдэн зам байвал санамсаргүйгээр явах замаа сонгоно (оройгоос гарсан ирмэг нь нэгээс их орой дээр байх үедээ). Мэдээж Робот графын чиглэлтэй ирмэгүүдийн дагуу л хөдлөнө.

Та ийм шинж чанартай роботыг төсөөлж чадаж байна уу? Энэ нь яагаад энэ роботууд маш хямдхан зарагддаг шалтгаан юм. Мэдээж mzry1992 шиг мөнгө багатай хүн шиг хүмүүст зориулсан. mzry1992 иймэрхүү роботтой ба тэр роботоо чиглэлтэй графын $s$ оройгоос $t$ оройруу өөрийгөө устгахгүйгээр аюулгүй аваачихыг хүсэж байна. Азаар тэр роботоо орой бүр дээр тусгай удирдлагаар хөдөлгөж чадна. Тусгай удирдлага нь явах олон зам гарч ирэхэд аль замаар нь явахыг үзүүлнэ (робот хууль 3-н дагуу санамсаргүйгээр явахаас сэргийлнэ). Робот $t$ оройд хүрэх үед mzry1992 роботыг графаас шууд авна. $s$-с $t$ хүртэлх зам оршин байвал тэр зорилгодоо хүрэх замыг үргэлж олж чадна ($t$ оройгоос гарсан ирмэгүүдийн тоо тэг байсан ч үгүй байсан ч).

Жишээ 2

Гэсэн ч илгээх дарааллууд их үнэтэй ба таны ажил бол mzry1992-т хамгийн муу тохиолдолд илгээхэд хэрэгтэй дарааллуудын хамгийн бага тоог олох юм. mzry1992 робот граф дээр явж байх үед дарааллуудыг өгч чадна. Бодлогын хэсгийг илүү сайн ойлгохын тулд эхний жишээг харна уу.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ($1 ≤ n ≤ 10^{6}$) ба $m$ ($1 ≤ m ≤ 10^{6}$) байх буюу харгалзан графын оройнуудын тоо болон ирмэгүүдийн тоо байна. Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$; $v_{i} ≠ u_{i}$) байх ба энэ тоонууд нь $u_{i}$ оройгоос $v_{i}$ оройруу чиглэсэн ирмэг байгааг илтгэнэ. Сүүлийн мөрөнд хоёр бүхэл тоон утга $s$ ба $t$ ($1 ≤ s, t ≤ n$) байна.

Өөррүүгээ чиглэсэн давталт болон давхар ирмэг байхгүй.

Гаралт

Зорилгодоо хүрэх зам байвал хамгийн муу тохиолдолд шаардлагатай дарааллуудын хамгийн бага тоог хэвлэ. Бусад тохиолдолд -1-г хэвлэ.

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

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

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

Тэмдэглэл

Эхний жишээг авч үзье. Анх робот 1 орой дээр байна. Тэгээд эхний алхамдаа робот 2 эсвэл 3 оройруу очиж чадна. Робот аль оройг сонгох нь хамаагүй ба mzry1992 роботод дараалал өгөх ёстой. Энэ дараалал нь 4 оройруу явах байна. Хэрвээ mzry1992 роботод 2 эсвэл 3 орой дээр байхад нь дараалал өгөхгүй бол робот Хууль 3-н дагуу "муу" гадагшаа чиглэсэн ирмэгийг сонгож болно. Ингээд хариулт нэг байна.

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