I. Вагон

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

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

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

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

Берланд-ын S* гэх нэгэн хотод нэгэн вагоны хөдөлгүүрийн төв болон ганцхан вагон байдаг байв. Уг төвд 3 хүн ажилладаг бөгөөд тухайлбал вагоны жолооч, тасалбар түгээгч болон уг төвийн ахлагч нар юм. Вагон өглөө бүр хөдөлгүүрийн төвөөс эхлэн хөдлөх бөгөөд өөрийн гогцоо хэлбэрийн маршрутын дагуу явдаг байв. Вагон өөрийн маршрутаа яг $c$ минутад туулдаг байжээ. Хөдөлгүүрийн төвийн ахлагч вагоны хөдөлгөөнийг удирддаг ба хөдөлгүүрийн төв вагоныг удирдаж байх зуур вагон $c$ минут тутамд гадагш гардаг байжээ. Өөрөөр хэлбэл $c$ минутад маршрутаа туулан эргэн хөдөлгүүрийн төвд ирэх бөгөөд дахин хөдөлгүүрийн төвөөс эхлэн хөдлөх юм. Хэрэв вагоны жолооч 1-л секунд хоцорсон тохиолдолд ахлагч түүнд урамшуулал олгодоггүй байжээ.

Уг төвийн үйл ажиллагаа дээрх байдлаар явагддаг байсан бөгөөд үүний дараа Берланд-ын улсын төсвийн газраас S*** хотод илүү олон вагоны зам бариулахаар мөнгө өгчээ. Ийм зүйл заримдаа болдог байв. Өөрөөр хэлбэр улсын төсөвт энэ бүхнийг тусгасан гэсэн үг юм. Вагоны замуудыг дахин барьсан бөгөөд эдгээр замууд нь нэгэн том сүлжээг үүсгэжээ. Өмнөх гогцоо хэлбэртэй маршрут нь магадгүй одоо байхгүй болсон ба S*** одоо $n$ ширхэг замын уулзвар болон хос замын уулзваруудыг холбох $m$ ширхэг вагоны замтай болсон байв. Берланд дахь замын хөдөлгөөн нь нэг урсгалтай байдаг учраас вагон нь вагоны зам болгон дээр зөвхөн нэг чиглэлийн дагуу л хөдөлж чадах юм. 2 ширхэг замын уулзварын хооронд магадгүй хэд хэдэн вагоны зам байж болох бөгөөд эдгээр замууд нэг чиглэлийн эсвэл эсрэг урсгалын замууд байх юм. Вагоны зам болгон нь ялгаатай 2 замын уулзварыг холбох бөгөөд замын уулзвар болгоны хувьд дор хаяж нэг ширхэг уг уулзвараас гарч буй вагоны зам оршин байх юм.

Ингэснээр вагоны замууд баригдсан боловч хэний ч санаанд S*-дахь вагоны тоог нэмэгдүүлэх бодол орж ирээгүй байв! Иймд вагон нь үргэлжлүүлэн ганцаараа явсаар байх бөгөөд одоо жолооч хөдөлгүүрийн төвийн ахлагчийн удирдлагаас салах маш сайхан боломжтой болжээ. Одоогийн вагоны замын сүлжээнээс хамаарч тэрээр өөрийн вагоны маршрутаа дурын байдлаар сонгох боломжтой байв! Одоо тэрээр замын уулзвар болгон дээрээс өөрийн явах замыг дурын байдлаар сонгож болох бөгөөд вагон нь өөрийн эргэж ирж чадахгүй газраасаа (одоо замууд нь нэг л урсгалтай учраас зарим цэгээс эхлэн яваад тухайн цэг дээр эргэн ирж чадахгүй байх боломжтой юм) хүртэл S***-ын ямар нэгэн хэсгүүд уруу явж болох байв. Жолооч аз туршихаас айхгүй байгаа юм. Учир нь тэрээр шөнө болж хот унтах үед өөрийн явсан вагоны замуудынхаа эсрэг чиглэлийн дагуу явсаар хөдөлгүүрийн төвд хүрч чадна. Тодруулбал шөнө болох үед хотын дүрэм үйлчлэхгүй ба вагоны замаар ямар ч чиглэлд явах ажээ.

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

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

Хөдөлгүүрийн төв байрлаж буй замын уулзвар дээр заавал камер байрласан байх ёстой бөгөөд энэ нь ахлагчийг террористуудын боломжит халдлагаас сэргийлэх зорилготой юм. Бүх боломжит төлөвлөгөөнүүд дундаас ахлагч боломжит хамгийн их $t$-ын утга бүхий төлөвлөгөөг сонгох юм. Учир нь тэрээр өөрийн дуртай TV нэвтрүүлгээсээ холдох дургүй бөгөөд аргагүйн эрхэнд камер шалгах хэрэгтэй болжээ. Хэрэв ийм байх төлөвлөгөө нь цор ганц биш байвал хамгийн цөөн тооны камер ашиглах төлөвлөгөөг сонгоно. Тэгвэл ийм байх төлөвлөгөөг олж өгнө үү.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$ болон $m$ ($2 ≤ n, m ≤ 10^{5}$) өгөгдөх ба эдгээр нь харгалзан S*-дэх замын уулзваруудын тоо болон вагоны замын тоог тус тус илэрхийлнэ. Дараагийн $m$ мөрөнд вагоны замуудын тайлбар "$u$ $v$" хэлбэртэйгээр өгөгдөх ба энд $u$ нь уг вагоны замын эхлэл болж буй уулзвар бөгөөд $v$ нь төгсгөл болж буй уулзварыг илэрхийлнэ. Замын уулзварууд нь $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан байх бөгөөд хөдөлгүүрийн төв нь $1$ дугаартай замын уулзвар дээр байх юм.

Гаралт

Гаралтын эхний мөрөнд $t$-ын утгыг хэвлэнэ үү. Дараагийн мөрөнд $k$-ын утгыг хэвлэх бөгөөд энэ нь нийт шаардлагатай камерын тоог илэрхийлнэ. Дараагийн мөрөнд камеруудыг байрлуулах ёстой замын уулзваруудын дугааруудыг зайгаар тусгаарлан хэвлэнэ үү. Эдгээр тоонуудыг хэвлэхдээ өсөх дарааллын дагуу хэвлэнэ.

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

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

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