D. Робот рэп тулааны дүнгийн сурвалжлага

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

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

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

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

Фермер Жон Бовиниа-ын үл мэдэгдэх хэсэгт өөрийн фермээ дахих барьж байхад, Бэссие ээлжийн ажлуудаас гарахыг оролдож байв.Түүний шинэ зугаа нь сурвалжлагч болох ба тэрээр программчлалын тэмцээний дүнг аль болох хурдан мэдэх хэрэгтэй байв.Тэрээр 2016 оны Робот рэп тулааныг ажиглаж байхдаа бүх роботууд нь тодорхойлогдсон алгоритмуудын дагуу ажилладаг болохыг анзаарчээ.Ялангуяа, хэрэв $i$-дахь робот нь $j$-дахь роботоос илүү их чадварын түвшинтэй байвал $i$-дахь робот нь $j$-дахь роботыг дийлэх юм.Мөн хэрэв $i$-дахь робот нь нь $j$-дахь роботыг дийлэх ба $j$-дахь робот нь $k$-дахь роботыг дийлж байвал $i$-дахь нь $k$-дахь роботоо дийлнэ.Рэп хийх нь үнэхээр уран чадварлаг урлаг учраас, 2 робот ижилхэн чадварын түвшинтэй байхгүй юм.

Тэдгээр роботуудын тулалдсан дарааллаар өгөгдөх рэп тулааны дүн өгөгдсөн бөгөөд Бэссие бүх роботуудыг чадварын түвшингээр нь дараалалд оруулан байрлуулахаас өмнө хийгдэх эхний хэдэн рэп тулааны хамгийн бага тоог тодорхойлно уу.

Оролт

Эхний мөрөнд 2 бүхэл тоо өгөгдөнө, роботын тоо $n$ ($2 ≤ n ≤ 100 000$) болон тулааны тоо $m$ () өгөгдөнө.

Дараагийн $m$ мөрөнд эзэлсэн байрлалынх дагуу рэп тулаануудын дүнг дүрсэлнэ.Тус бүр нь 2 бүхэл тоо $u_{i}$ болон $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$, $u_{i} ≠ v_{i}$)-аас тогтох ба $u_{i}$-дахь робот нь $i$-дахь рэп тулаанд $v_{i}$-дахь роботыг ялсан гэдгийг илэрхийлнэ.Ямар ч 2 рэп тулаанд ижил хос роботууд оролцоогүй байна.

Бүх $m$ холбоог хангах ядаж ганц роботуудын дараалал оршин байна.

Гаралт

Эхний $k$ рэп тулаанаар роботуудын чадварын түвшингийн дарааллыг цор ганц байдлаар тодорхойлох хамгийн бага $k$-г хэвлэнэ.Хэрэв бүх $m$ холбоог хангах нэгээс олон дараалал оршин байвал $-1$ гэж хэвлэнэ үү.

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

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

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

Тэмдэглэл

Эхний жишээнд роботууд нь хүчтэйгээсээ сул хүртэл дараалал нь $(4, 2, 1, 3)$ ба Бэссие эхний 4-н рэп тулааны дүнгийн дараа ингэж дүгнэж чадах юм.

2-дахь жишээнд, 2 рэп тулааны дараа $(1, 3, 2)$ болон $(3, 1, 2)$ нь 2-уулаа хүчтэйгээсээ сул уруугаа байх боломжит роботуудын дараалал юм.

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