Snowy Roads
Турнир за Купата на Декана, 2012
Time Limit: 0.2s, Memory Limit: 64MiB
Зима е. Наскоро падна първия сняг, като общината се захвана веднага за работа – да коментира по най-различни медии колко много снегорини чистят улиците и т.н.

Всъщност Ели забеляза, че всеки час бива изчистена точно една улица. Тя следи новините и си записва в какъв ред улиците биват изчистени. След изчистването и на последната от тях, Ели реши да провери колко часа е отнело на общината да възстановят възможността за достигане на всяко кръстовище от всяко друго в града, движейки се само по изчистени улици. Считаме, че всички улици в града са двупосочни.

Помогнете ѝ, като по даден брой кръстовища и списък с реда на изчистване на улиците, определите колко часа е отнело това.
Вход
Първият ред на стандартния вход ще съдържащ две цели числа N и M – съответно броя кръстовища и броя улици в града. На следващите M реда има по една двойка цели числа Ai и Bi, указващи, че в i-тия час е била изчистена улицата между кръстовища с номера Ai и Bi.
Изход
На единствен ред на стандартния изход изведете едно цяло число – колко часа са изминали преди да е възстановена свързаността на града. Ако дори след изчистването на последната улица в списъка има двойка кръстовища, които са недостижими едно от друго, изведете -1.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 0 ≤ M ≤ 300,000
  • 1 ≤ Ai, BiN
Примерен Вход Примерен Изход
6 8 1 2 4 5 2 5 3 1 3 5 6 5 4 6 3 4 6
Мрън!